【力扣】 【 131 】 【中等】 分割回文串

这道题难点分为两部分：找出 回文串 和 分割字符串 ，这里用 动态规划 解决第一个问题，使用 回溯 解决第二个问题

使用动态规划解决找出回文串

• 首先我们要明白为什么要在这里使用动态规划

假如我们使用循环去找回文串，那么会有重复的判断，比如 abccba ，从第一位开始， abccba 是回文串，这种判断是基于 bccb 和 cc 是回文串，但是当遍历到 b 和 c 时，又会判断 bccb 和 cc 是否是回文串。

所以使用动态规划能避免重复判断。

• 那么针对这道题，我们如何进行分解

1. 每个字符都是回文串，比如： a , b 。
2. 如果两个字符相同，并且中间的字符串是回文串，那么这条字符串一定是回文串，比如： aba , abba

既然如此，我们就能从 b ==> aba ，再到其他回文串判断

总结为：只要两个字符间的字符串是回文串，并且两个字符相同，那么就为回文串

整理为表格

a 的本身是回文串

首尾字符 a 和 b 不相同，即使中间的字符是回文串，aab 也不是回文串

使用回溯分割字符串

分割字符串时有将单个字符作为一个回文串和将字符串当做一个回文串，因此在回溯后，需要恢复回溯前的状态

代码实现

class Solution {
    boolean[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();
    List<String> ans = new ArrayList<String>();
    int n;

    public List<List<String>> partition(String s) {
        n = s.length();
        f = new boolean[n][n]; 
        //初始化
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);
        }
        //字符本身就是一个回文串，那么就应该把表格的对角线变为true，因为之前已经初始化为true，因此这里不用再判断字符本身
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }
    //回溯
    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }
}