131-132、分割回文串

leetcode

Created At : 2020-07-26 00:19

Count:949 Views 👀 :

Comment:

分割回文串
示例 1：
示例 2：
思路
1. 回溯 + 动态规划预处理
2. 优化回溯 + 记忆化搜索
分割回文串2
1. 示例:
动态规划
代码

分割回文串

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

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

链接：https://leetcode.cn/problems/palindrome-partitioning-ii/description/

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

思路

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

$$
f(i,j)=\begin{cases}
True & i>=j \
f(i+1,j-1) \land (s[i] == s[j])& otherwise
\end{cases}
$$

回溯 + 动态规划预处理

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);
        }


        // 扫描一遍，
        for (int i = n - 1; 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) {
            // s[i]~[j] 是回文串
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }
}

优化回溯 + 记忆化搜索

方法一中的动态规划预处理计算出了任意的 s[i..j] 是否为回文串，我们也可以将这一步改为记忆化搜索。

class Solution {
    int[][] 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 int[n][n];

        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 (isPalindrome(s, i, j) == 1) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }

    // 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
    public int isPalindrome(String s, int i, int j) {
        if (f[i][j] != 0) {
            return f[i][j];
        }
        if (i >= j) {
            f[i][j] = 1;
        } else if (s.charAt(i) == s.charAt(j)) {
            f[i][j] = isPalindrome(s, i + 1, j - 1);
        } else {
            f[i][j] = -1;
        }
        return f[i][j];
    }
}

分割回文串2

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

动态规划

代码

// 自底向上
public int minCut(String s) {
    int n = s.length();
    // 最每一处之前的最小分割次数
    int[] minS = new int[n];
    // 记录和更新回文串
    boolean[][] dp = new boolean[n][n];
    for (int i = 0;i < n;i++) {
        // 初始化min_s
        minS[i] = i;
        for (int j = 0; j <= i;j++) {
            //  相等 且距离为 0 或 1 且内部字串是回文串
            if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j+1][i-1])) {
                // 更新回文串记录
                dp[j][i] = true;
                // 更新回文串最小分割数, j == 0 意味着还没开始
                minS[i] = j == 0 ? 0 : Math.min(minS[i],minS[j - 1] + 1);
            }
        }
    }
    return minS[n - 1];
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com