分割回文串

LeetCode每日一题，131. Palindrome Partitioning

先看题目描述

大意就是给定一个字符串 s，让我们将 s 划分为多个回文子串，返回所有的划分方式

算法和思路

回溯 + 动态规划预处理

我们首先使用动态规划对字符串 s 进行预处理，布尔数组 dp[i][j] 代表子串 s[i：j] 是否为回文子串

状态转移方程为 dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]

将 dp 数组预先构建好后便可在 O(1) 的时间内判断 s 的某子串是否为回文串

由于需要求出字符串 s 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方案并进行判断

设当前搜索到字符串的第 i 个字符，且 s[0：i - 1] 位置的所有字符已被分割成若干个回文子串。接下来我们从 i 开始，从小到大依次枚举 j，通过 dp 数组判断 s[i：j] 是否为回文串，若为回文串，那么将其加入答案数组 temp，并以 j + 1 作为新的 i 进行下一轮搜索，并在未来的回溯时将 s[i：j] 从答案中移除

当搜索完字符串 s 的最后一个字符时，那么就找到了一种满足要求的分割方法

算法和源码

回溯 + 动态规划预处理

class Solution {
    private int len;
    private boolean[][] dp;
    private List<String> temp = new ArrayList<>();
    private List<List<String>> ans = new ArrayList<>();

    public List<List<String>> partition(String s) {
        len = s.length();
        dp = new boolean[len][len];
        char[] cs = s.toCharArray();
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (j - i <= 2) {
                    dp[i][j] = cs[i] == cs[j];
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && cs[i] == cs[j];
                }
            }
        }
        dfs(s, 0);
        return ans;
    }

    private void dfs(String s, int index) {
        if (index == len) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < len; i++) {
            if (dp[index][i]) {
                temp.add(s.substring(index, i + 1));
                dfs(s, i + 1);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

下面是自己一开始实现的方法，算法比较像是分治，虽然提交时通过了，但是效率很低，可能是由于往动态数组中存取子串的过程过于繁琐

class Solution {
    public List<List<String>> partition(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        char[] cs = s.toCharArray();
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                if (j - i <= 2) {
                    dp[i][j] = cs[i] == cs[j];
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && cs[i] == cs[j];
                }
            }
        }
        return partitionRecursively(s, 0, len - 1, dp);
    }

    public List<List<String>> partitionRecursively(String s, int left, int right, boolean[][] dp) {
        int len = right - left + 1;
        List<List<String>> ans = new ArrayList<>();
        if (len == 1) {
            List<String> temp = new ArrayList<>();
            temp.add(s.substring(left, left + 1));
            ans.add(temp);
            return ans;
        }
        for (int i = left; i < right; i++) {
            if (dp[left][i]) {
                List<List<String>> cur = partitionRecursively(s, i + 1, right, dp);
                for (List<String> l : cur) {
                    List<String> temp = new ArrayList<>();
                    temp.add(s.substring(left, i + 1));
                    for (String ss : l) {
                        temp.add(ss);
                    }
                    ans.add(temp);
                }
            }
        }
        if (dp[left][right]) {
            List<String> temp = new ArrayList<>();
            temp.add(s.substring(left, right + 1));
            ans.add(temp);
        }
        return ans;
    }
}