Leetcode--Java--131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：

输入：s = "a"
输出：[["a"]]

方法一：dfs + 双指针判断回文
方法二：dfs回溯 + 动态规划预处理优化

1. f[i][j]表示i ~ j这段是否为回文串。
2. dp遍历时先遍历j，这样才能保证算f[i][j]前f[i + 1][j - 1]已经算出来，因为j - 1在前面。

方法一：

class Solution {
    List> res = new ArrayList<>();
    public List> partition(String s) {
          int n = s.length();
          if (n == 0) return res;
          dfs(s, 0, new ArrayList());
          return res;
    }
    public void dfs(String s, int idx, ArrayList path) {
        int n = s.length();
        if (idx == s.length()) {
            res.add(new ArrayList(path));
        }
        for (int i = idx; i < s.length(); i ++ ) {
            //截取该字串，进行回文判断
            String sub = s.substring(idx, i + 1);
            if (check(sub)) {
                path.add(sub);
                dfs(s, i + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }
    public boolean check(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i ++;
            j --;
        }
        return true;
    }
}

方法二：

class Solution {
    List> res = new ArrayList<>();
    boolean f[][];
    public List> partition(String s) {
       int n = s.length();
       f = new boolean[n][n]; //f[i][j]表示 字串i~j是否是回文串
       //先遍历j，保证f[i + 1][j - 1]先算出来
       for (int j = 0; j < n; j ++ ) {
           for (int i = 0; i < n; i ++ ) {
               //单个字符肯定是回文
               if (i == j) {
                 f[i][j] = true;
               }  //字符相等的情况下才有回文
               else if (s.charAt(i) == s.charAt(j)){
                   //刚好相邻,或者中间段是回文
                   if (i + 1 > j - 1 || f[i + 1][j - 1]) 
                   f[i][j] = true;
               }
           }
       }
     dfs(s, 0, new ArrayList ());
     return res;
    }

    public void dfs(String s, int idx, List path) {
        if (idx == s.length()) {
            res.add(new ArrayList<>(path));
        }
        for (int i = idx; i < s.length(); i ++ ) {
            if (f[idx][i]) {
              path.add(s.substring(idx, i + 1));
              dfs(s, i + 1, path);
              path.remove(path.size() - 1);
            }
        }
    }
}