枚举法

枚举法与它的马甲们

DFS + Backtracking 的搜索量很大。如果每次 DFS 之前都要进行条件检查的话，优化条件函数可以显著提升程序速度。如 N-Queens 和 Palindrome Partitioning 还有 Sudoku Solver

Generate Parentheses

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);
        }

    }
}

Restore IP Addresses

依旧是 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;
    }
}

Palindrome Partitioning

一个比较简单暴力的搜索办法就是直接 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.5 n^2$ (矩阵沿对角线划分的一半区域)

 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);
        }
    }

}

Letter Combinations of a Phone Number

有个小地方要注意，终止条件是

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 "";
    }
}