面试题85：
问题：
输入一个正整数n，输出所有包含n个左括号和n个右括号的组合，要求每个组合的左括号和右括号匹配。
解决方案：
使用回溯法。因为要生成n个左括号和n个右括号，故需要走2n步，每一步生成一个括号，每一步都面临两个选项，既可能生成左括号也可能生成右括号。有限制条件，第一：左括号和右括号的个数不能大于n；第二：已生成右括号的个数不能大于已生成左括号。
源代码：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new LinkedList<>();
dfs(n,n,"",result);
return result;
}
//left表示未生成左括号个数、right表示未生成右括号个数
private void dfs(int left,int right,String s,List<String> result){
if(left == 0 && right == 0){
result.add(s);
return;
}
if(left > 0){
dfs(left-1,right,s + "(",result);
}
//当生成左括号的个数大于生成右括号的个数时，出现生成右括号的情况。
if(left < right){
dfs(left,right-1,s+")",result);
}
}
}
面试题86：
问题：
输入一个字符串，要求将它分割成若干子字符串，使每个子字符串都是回文。
解决方案：
使用回溯法。当处理到字符串中的某个字符时，如果包括该字符在内后面还有n个字符，那么此时面临n个选项，即分割出长度为1的子字符串（只包含该字符）、分割出长度为2子字符串（即包含该字符及它后面的一个字符），以此类推，分割出长度为n的子字符串（即包含该字符在内的后面的所有字符）。由于题目要求分割出来的每个子字符串都是回文，因此需要逐一判断这n个子字符串是不是回文，只有回文子字符串才是符合条件的分割。分割出一段回文子字符串之后，接着分割后面的字符串。
源代码：
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> result = new LinkedList<>();
dfs(s,0,new LinkedList<>(),result);
return result;
}
private void dfs(String s,int start,LinkedList<String> list,List<List<String>> result){
if(start == s.length()){
result.add(new LinkedList<>(list));
}else{
//分割出包括该字符在内后面还有n个字符，长度为1的子字符串（只包含该字符）、分割出长度为2子字符串（即包含该字符及它后面的一个字符）。
for(int i = start;i < s.length();i++){
if(isBack(s,start,i)){
list.add(s.substring(start,i+1));
//继续对分割剩余部分进行判断
dfs(s,i+1,list,result);
list.removeLast();
}
}
}
}
//判断从字符串str下标start到end的子字符串是否是回文字符串。
private boolean isBack(String str,int start,int end){
while(start < end){
if(str.charAt(start++) != str.charAt(end--)){
return false;
}
}
return true;
}
}
面试题87：
问题：
输入一个只包含数字的字符串，列出所有可能恢复出来的IP地址。
解决方案：
使用回溯法。逐个扫描输入字符串中的字符以恢复IP地址。针对字符串中的每个数字，通常面临两个选项。第1个选项是将当前字符拼接到当前分段数字的末尾，拼接之后的数字应该在0到255之间。第2个选项是当前字符作为一个新的分段数字的开始。需要注意的是，一个IP地址最多只有4个分段数字，并且当开始一个新的分段数字时前一个分段数字不能是空的。
源代码：
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new LinkedList<>();
dfs(s,0,0,"","",result);
return result;
}
//i用于记录已经扫描到字符串的下标、segI表示当前分段数字的下标、seg表示当前分段字符串、ip表示已经拼接好的部分IP地址
private void dfs(String s,int i,int segI,String seg,String ip,List<String> result){
if(i == s.length() && segI == 3 && isValidSeg(seg)){
result.add(ip + seg);
//例如字符串s为10203040
}else if(i < s.length() && segI <= 3){
//当ch为2时，seg为10
char ch = s.charAt(i);
if(isValidSeg(seg + ch)){
//情况一：添加当前char字符到该分段，seg字符串变为102
dfs(s,i+1,segI,seg + ch,ip,result);
}
if(seg.length() > 0 && segI < 3){
//情况二：不添加当前char字符到该分段，seg字符串变为2，IP地址为10.
dfs(s,i + 1,segI + 1,"" + ch,ip + seg + ".",result);
}
}
}
//判断当前分段数字是否有效
private boolean isValidSeg(String seg){
return Integer.valueOf(seg) <= 255 && (seg.equals("0") || seg.charAt(0) != '0');
}
}