【leetcode hot 100 131】分割回文串

解法一：回溯法+动态规划法

回溯法：

• 假设我们当前搜索到字符串的第 i 个字符，且 s[0…i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 j，使得 s[i…j] 是一个回文串。
• 因此，我们可以从 i 开始，从小到大依次枚举 j。对于当前枚举的 j 值，我们使用双指针的方法判断 s[i…j] 是否为回文串：如果 s[i…j] 是回文串，那么就将其加入答案数组 ans 中，并以 j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i…j] 从 ans 中移除。
• 如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。

动态规划法：

• 将字符串 s 的每个子串 s[i…j] 是否为回文串预处理出来，使用动态规划即可。设 f(i,j) 表示 s[i…j] 是否为回文串，那么有状态转移方程：
  

class Solution {
    List<List<String>> result = new ArrayList<List<String>>();
    List<String> temp = new ArrayList<String>();
    boolean[][] huiwen;
    int n;
    public List<List<String>> partition(String s) {
        // 初始化
        n = s.length();
        huiwen = new boolean[n][n]; // huiwen[i][j]用于记录s[i...j]是否是回文串

        // 让i<j时，huiwen[i][j]=true，确保huiwen[i+1][j-1]的计算
        for(int i=0; i<n; i++){
            Arrays.fill(huiwen[i], true);
        }

        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){ //不能为j=i,否则不为子串
                huiwen[i][j] = (s.charAt(i)==s.charAt(j)) && huiwen[i+1][j-1];
            }
        }
        
        backtrace(s, 0);
        return result;
    }

    public void backtrace(String s, int num){
        // num表示处理到s的第几个数
        if(num==n){
            result.add(new ArrayList<String>(temp));
            return;
        }
        for(int j=num; j<n; j++){
            // num,j表示s[num...j]
            if(huiwen[num][j]){
                temp.add(s.substring(num, j+1));
                backtrace(s, j+1);
                temp.remove(temp.size()-1);
            }
        }
    }
}

注意：

• 让i<j时，huiwen[i][j]=true，确保huiwen[i+1][j-1]的计算
• 在设置huiwen[i][j] = (s.charAt(i)==s.charAt(j)) && huiwen[i+1][j-1]时，j要从i+1开始，不能为j=i，否则不为子串
• 在回溯的for循环中，num,j表示子串s[num...j]