Leetcode - 131. 分割回文串

class Solution {

    // 首先，找到字符串s中所有是回文的子串，然后使用回溯法进行回文切分
    public List<List<String>> partition(String s) {
        int length = s.length();
        char[] arr = s.toCharArray();
        List<List<String>> ret = new ArrayList<>();

        // dp[l][r]表示字符串s的[l, r]区间上的子串是否为回文
        // 注意dp[l][r]的动态转移方程中包含dp[l + 1][r - 1]
        // 因此需要保证在判断dp[l][r]时dp[l + 1][r - 1]已经被置为正确的值
        boolean[][] dp = new boolean[length][length];

        for (int r = 0; r < length; r++) {
            
            // 长度为1的字符串一定是回文
            dp[r][r] = true;
            
            for (int l = r - 1; l >= 0; l--) {

                // 如果l和r指向的字符不同，则当前子串肯定不是回文
                // 如果l和r指向的字符相同，则r - l <= 2时当前子串是回文
                // 如果l和r指向的字符相同，且r - l > 2，那么dp[l][r]取决于dp[l + 1][r - 1]
                dp[l][r] = arr[l] != arr[r] ? false : (r - l <= 2 ? true : dp[l + 1][r - 1]);
            }
        }

        // 使用回溯法
        search(s, 0, dp, new LinkedList<>(), ret);
        return ret;
    }

    // 回溯法，该方法的主要作用是从字符串s的下标begin开始找到一个回文，将它放入split集合中
    private void search(String s, int begin, boolean[][] dp, LinkedList<String> split, List<List<String>> ret) {
        int length = s.length();

        // 如果开始的下标正好为字符串的长度，说明找到了一个可行的分割方案
        if (begin == length) {
            ret.add(new ArrayList(split));
            return;
        }

        // 否则，从begin开始寻找回文，将该回文放入split集合中
        for (int i = begin; i < length; i++){
            
            // 不是回文，则跳过
            if (!dp[begin][i]) {
                continue;
            }
            
            // 将回文添加到split集合中
            split.addLast(s.substring(begin, i + 1));
            
            // 继续往下搜索
            search(s, i + 1, dp, split, ret);
            
            // 回溯
            split.pollLast();
        }
    }
}