枚举法
DFS和backtracking的搜索量巨大。如果每次DFS递归前都要进行条件检查，那么优化条件函数就能显著地提高程序性能。
这道题我本来想用一个count做stack变量的。但是后来想一下，只有left-right的相对差值，并没有left和right的具体个数，不是太好判断left和right的quota是否已经用光。于是还是决定用两个int变量：left和right来存已经用掉的'('和')'的个数。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
if (n <= 0)
return res;
backtrack(res, new StringBuilder(), 0, 0, n);
return res;
}
public void backtrack(List<String> res, StringBuilder sb, int left, int right, int n){
if (left == n && right == n){
res.add(sb.toString());
return;
}
if (left < n && left >= right){
sb.add('(');
backtrack(res, sb, left+1, right, n);
sb.setLength(sb.length()-1);
}
if (right < n && left > right){
sb.add(')');
backtrack(res, sb, left, right+1, n);
sb.setLength(sb.length()-1);
}
}
}
这个问题比较tricky的地方是什么时候break：
- 当前考虑的三个数中第一个是'0'，而且已经考虑到第二个数
- 当前考虑的三个数连起来之后大于255
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if (s == null || s.length() < 4)
return res;
backtrack(res, new StringBuilder(), 0, 0, s);
return res;
}
public void backtrack(List<String> res, StringBuilder sb, int count, int first_index, String s){
// if (count == 4 && first_index == s.length()){
if (count == 4){
if (first_index == s.length())
res.add(sb.toString());
return;
}
int len = sb.length();
for (int i = first_index; i < first_index + 3 && i < s.length(); i++){
String num = s.substring(first_index, i+1);
if (i > first_index && s.charAt(first_index) == '0' || Integer.parseInt(num) > 255)
break;
sb.append(s.substring(first_index, i+1));
if (count < 3) sb.append('.');
backtrack(res, sb, count+1, i+1, s);
sb.setLength(len);
}
}
}
发现一个规律。。。
只要是跟palindrom有关的题，都可以用expand的方法做，而且还很高效。
这道题如果暴力做（backtracking，每一个substring都用isPalindrome检查一下），就会TLE。所以要想想更高效的办法：
首先用expand的方法找出来s所有palindrome substring，结果存在boolean[][] palin里，其中如果palin[i][j] == true，表示s.substring(i, j+1)是palindrome。然后搜索过程就变得简单了：只需要用一个first_index来记录第一个可用的字符位置就行了，然后向后遍历找到一个palindrom substring，再递归backtrack。
class Solution {
static boolean[][] palin;
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if (s == null || s.length() == 0)
return res;
int n = s.length();
palin = new boolean[n][n];
for (int i = 0; i < n; i++){
expand(i, i, s);
expand(i, i+1, s);
}
backtrack(res, new ArrayList<>(), 0, s);
return res;
}
public void expand(int i, int j, String s){
while (i >= 0 && j < s.length()){
if (s.charAt(i) == s.charAt(j))
palin[i][j] = true;
else
return;
i--;
j++;
}
}
public void backtrack(List<List<String>> res, List<String> l, int first_index, String s){
if (first_index == s.length()){
res.add(new ArrayList<>(l));
return;
}
for (int i = first_index; i < s.length(); i++){
if (palin[first_index][i]){
l.add(s.substring(first_index, i+1));
backtrack(res, l, i+1, s);
l.remove(l.size()-1);
}
}
}
}
17. Letter Combinations of a Phone Number
（这道题感觉十分经典啊，FB出国，Oscar也出过。）
这道题有两种做法，都比较intuitive。第一种是backtracking：
class Solution {
static String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.length() == 0)
return res;
backtrack(res, new StringBuilder(), digits, 0);
return res;
}
public void backtrack(List<String> res, StringBuilder sb, String digits, int first_index){
if (first_index == digits.length()){
res.add(sb.toString());
return;
}
int len = sb.length();
for (char ch : mapping[digits.charAt(first_index)-'0'].toCharArray()){
sb.append(ch);
backtrack(res, sb, digits, first_index+1);
sb.setLength(len);
}
}
}
另一种是BFS：
class Solution {
public List<String> letterCombinations(String digits) {
String[] map = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<>();
if (digits.equals("")) return res;
res.add("");
for (int digitIdx = 0; digitIdx < digits.length(); digitIdx++){
int size = res.size();
for (int i = 0; i < size; i++){
String base = res.remove(0);
char[] charOptions = map[digits.charAt(digitIdx)-'0'].toCharArray();
for (char option : charOptions)
res.add(base + option);
}
}
return res;
}
}