枚举法与它的马甲们
Too trivial. 这题和二叉树其实挺像的，因为在每一个位置都只有两种可能 "(" 和 ")".
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<String>();
dfs(list, new StringBuilder(), n, n);
return list;
}
private void dfs(List<String> list, StringBuilder sb, int left, int right){
if(left == 0 && right == 0){
list.add(sb.toString());
return;
}
int length = sb.length();
if(left > 0){
sb.append('(');
dfs(list, sb, left - 1, right);
sb.setLength(length);
}
if(right > left){
sb.append(')');
dfs(list, sb, left, right - 1);
sb.setLength(length);
}
}
}
依旧是 DFS + Backtracking，每一步有三种可能：选一位数，两位数，还有三位数。
一个需要注意的边界条件是当选取多位数时，第一位不能是0，因为 '020' 或 '05' 都不是有效的 IP 地址。
当 DFS 的可能性比较多，而且只在 index 上有区别的时候，用 for 循环就好了。
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> list = new ArrayList<String>();
if(s.length() > 12) return list;
dfs(list, new StringBuilder(), s, 0, 0);
return list;
}
private void dfs(List<String> list, StringBuilder sb,
String s, int ipIndex, int strIndex){
if(ipIndex > 4) return;
if(ipIndex == 4 && strIndex == s.length()){
sb.setLength(sb.length() - 1);
list.add(sb.toString());
return;
}
int length = sb.length();
// Add one digit number
for(int i = 0; i < 3; i++){
if(strIndex + i < s.length()){
String substr = s.substring(strIndex, strIndex + 1 + i);
if(isValid(substr)){
sb.append(substr);
sb.append('.');
dfs(list, sb, s, ipIndex + 1, strIndex + 1 + i);
sb.setLength(length);
}
}
}
}
private boolean isValid(String str){
if(str.charAt(0) == '0'){
return str.equals("0");
}
int num = Integer.parseInt(str);
if(num > 0 && num <= 255) return true;
return false;
}
}
一个比较简单暴力的搜索办法就是直接 DFS + Backtracking，每一步上需要考虑的字问题数量和当前字符串剩余长度相等。 这个解法是过不了 LeetCode OJ 的，会超时。
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> rst = new ArrayList<List<String>>();
dfs(rst, new ArrayList<String>(), s, 0);
return rst;
}
private void dfs(List<List<String>> rst, List<String> list, String s, int index){
if(index == s.length()){
rst.add(new ArrayList<String>(list));
return;
}
for(int i = index; i < s.length(); i++){
String substr = s.substring(index, i + 1);
if(!isPalindrome(substr)) continue;
list.add(substr);
dfs(rst, list, s, i + 1);
list.remove(list.size() - 1);
}
}
private boolean isPalindrome(String str){
int left = 0;
int right = str.length() - 1;
while(left > right){
if(str.charAt(left) != str.charAt(right)) return false;
left ++;
right --;
}
return true;
}
}
于是发现每次都要跑一个 isPalindrome() 太耗时间了，同一个字符串会被检查很多次，不如用 DP 把任意两个 index 之间的字符串缓存下，加速 isPalindrome() 的验证。
然并卵，还是超时。
主要原因在于，从每一个字符作为起点向两边扩张的赋值方式，还是不够快。
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> rst = new ArrayList<List<String>>();
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++){
dp[i][i] = true;
int left = i - 1;
int right = i + 1;
while(left >= 0 && right < s.length()){
if(s.charAt(left) == s.charAt(right))
dp[left][right] = true;
left --;
right ++;
}
}
dfs(rst, new ArrayList<String>(), s, 0, dp);
return rst;
}
private void dfs(List<List<String>> rst, List<String> list, String s, int index, boolean[][] dp){
if(index == s.length()){
rst.add(new ArrayList<String>(list));
return;
}
for(int i = index; i < s.length(); i++){
if(!dp[index][i]) continue;
String substr = s.substring(index, i + 1);
list.add(substr);
dfs(rst, list, s, i + 1, dp);
list.remove(list.size() - 1);
}
}
}
于是就有了这段代码，思路参考了 LeetCode 论坛，里面的小伙伴们好机智啊。
dp[i][j] 代表从index i ~ j 的字符串是不是 palindrome. dp[i][j] = dp[j][i].
其实也可以只填 dp[i][j]，也就是矩阵的 lower half 三角形，不过到时候调用的时候要注意放 index 的先后顺序，不然结果会错。求稳的话，就一次都设一样的吧。
(7/6 号) 回头复习过程中发现，这就是做 search 类题，遇到了记忆化搜索啊。
在 palindrome 问题中，子串之间有天然的 optimal substructure，很适合利用 dp 做预处理解决。
建立一个 String 的所有 substring 是否为 palindrome 的矩阵，时间复杂度为等差数列，约为
0.5n2 (矩阵沿对角线划分的一半区域)
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> rst = new ArrayList<List<String>>();
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++){
for(int j = 0; j <= i; j++){
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[i - 1][j + 1]))
dp[i][j] = dp[j][i] = true;
}
}
dfs(rst, new ArrayList<String>(), s, 0, dp);
return rst;
}
private void dfs(List<List<String>> rst, List<String> list, String s, int index, boolean[][] dp){
if(index == s.length()){
rst.add(new ArrayList<String>(list));
return;
}
for(int i = index; i < s.length(); i++){
if(!dp[i][index]) continue;
String substr = s.substring(index, i + 1);
list.add(substr);
dfs(rst, list, s, i + 1, dp);
list.remove(list.size() - 1);
}
}
}
有个小地方要注意，终止条件是
sb.length() == digits.length()
而不是
pos >= digits.length()
不然在 test case 为 “22” 的时候在返回了所有正确答案之后会多出来一组 "a","b","c"
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> list = new ArrayList<String>();
if(digits == null || digits.length() == 0) return list;
dfs(list, new StringBuilder(), digits, 0);
return list;
}
private void dfs(List<String> list, StringBuilder sb, String digits, int pos){
if(sb.length() == digits.length()){
list.add(sb.toString());
return;
}
for(int i = pos; i < digits.length(); i++){
String str = getAlphabets(digits.charAt(i));
for(int j = 0; j < str.length(); j++){
int length = sb.length();
sb.append(str.charAt(j));
dfs(list, sb, digits, i + 1);
sb.setLength(length);
}
}
}
private String getAlphabets(Character digit){
if(digit == '2') return "abc";
if(digit == '3') return "def";
if(digit == '4') return "ghi";
if(digit == '5') return "jkl";
if(digit == '6') return "mno";
if(digit == '7') return "pqrs";
if(digit == '8') return "tuv";
if(digit == '9') return "wxyz";
return "";
}
}