[LeetCode] 132. 分割回文串 II

题目链接 : https://leetcode-cn.com/problems/palindrome-partitioning-ii/

题目描述:

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

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

示例:

输入: "aab"

输出: 1

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

思路:

动态规划,

思路一: 自顶向下

import functools

class Solution:

    @functools.lru_cache(None)

    def minCut(self, s: str) -> int:

        if s == s[::-1]:

            return 0

        ans = float("inf")

        for i in range(1, len(s) + 1):

            if s[:i] == s[:i][::-1]:

                ans = min(self.minCut(s[i:]) + 1, ans)

        return ans

思路二: 自底向上

可以通过5. 最长回文子串(题解链接)和131. 分割回文串(题解链接)看一下关于dp的写法

再用数组min_s记录到字符串到i位置需要分割次数.

class Solution:

    def minCut(self, s: str) -> int:

        min_s = list(range(len(s)))

        n = len(s)

        dp = [[False] * n for _ in range(n)]

        for i in range(n):

            for j in range(i+1):

                if s[i] == s[j] and (i - j < 2 or dp[j + 1][i - 1]):

                    dp[j][i] = True

                    # 说明不用分割

                    if j == 0:

                        min_s[i] = 0

                    else:

                        min_s[i] = min(min_s[i], min_s[j - 1] + 1)

        return min_s[-1]

java

class Solution {

    public int minCut(String s) {

        int n = s.length();

        int[] min_s = new int[n];

        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {

            min_s[i] = i;

            for (int j = 0; j <= i; j++) {

                if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[j + 1][i - 1])) {

                    dp[j][i] = true;

                    min_s[i] = j == 0 ? 0 : Math.min(min_s[i], min_s[j - 1] + 1);

                }

            }

        }

        return min_s[n - 1];

    }

}

巴特西

[LeetCode] 132. 分割回文串 II

题目描述:

示例:

思路:

最新文章

热门文章