刚看到这道题的时候没理解,想不出来,后来有人说跟leetcode316题有点像,感觉那个题目的描述清楚得多
我看题解里没人用递归的方法,这里提供一个,抛砖引玉
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Main solution = new Main();
Scanner reader = new Scanner(System.in);
String input = reader.next();
char ans = solution.main(input);
System.out.println(ans);
}
public char main(String input){
if(input == null || input.length() == 0){
return ' ';
}
if(input.length() == 1){
return input.charAt(0);
}
input = input.toLowerCase();
char ans = solution(new StringBuilder(input));
return ans;
}
private char solution(StringBuilder input){
String find = input.substring(0,1);
int find_index = input.lastIndexOf(find);
if(input.length() == 1 || input.lastIndexOf(input.substring(0,1))== 0){
// 边界条件,即字符串被切分到不能再切分了,只剩一个了,
// 或者说当前字符串的首字符在剩下的字符串里没有重复出现了,就返回当前字符
return input.charAt(0);
}
// 当前字符在后续字符串中重复出现了,所以这里可以分为两种情况,比较一下哪种的字典序更小,然后返回
// 1. 删掉后面出现的当前字符,然后把剩下的部分丢入递归继续判断
// 但是其实不用再判断了,这一段字符串能出现的最小字典序就是当前字符
char ans1 = input.charAt(0);
// 2. 删掉当前字符,然后把剩下的部分递归继续判断
char ans2 = solution(input.deleteCharAt(input.indexOf(input.substring(0,1))));
return ans1 < ans2 ? ans1 : ans2;
}
}