算法题--将字符串划分为若干个回文最少需要切几刀

image.png

0. 链接

题目链接

1. 题目

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

2. 思路1: 动态规划

1. 基本思路是:

• 先初始化最差情形，即dp[i] = i(i = 0~size-1), 即每个字母都自成一个回文, dp[i]表示从0到i构成的字符串划分为回文最少需要切几刀
• 再自i=1开始从左到右依次尝试以每个字母作为回文的中心点, 对于每个中心点mid, 向左向右尽量扩展到start, end, 每左右各扩展一格, 则更新dp[end] = min(dp[end], 1 + dp[start - 1] if start > 0 else 0), 表示截止到end所需切的最少刀数, 取决于当前是否选择切这一刀，选择的依据，就是能否使得dp[end]变小，这是典型的动态规范思路，即选择，并评价选择的结果优劣。
• 需要注意的是，对于中心点的选择，有可能是一个，也有可能是2个，比如abba回文就需要拿中间的bb作为中心点,往左往右可扩展方可, 处理方式即start, end = mid - 1, mid, 它担负的任务与上一步中一样，也是要尽量扩展回文长度, 然后尽量缩小dp[end]的值
• 最终只需要返回dp[size-1]即可

2. 分析:

• 过程中需要尝试以每个字母作为中心点的情形, 所以有一个n次循环, 对于每个中心点, 又要有左右扩展的尝试, 极端情况下，比如aaaaaa的情形，每次左右扩展, 都可能到边界, 因此也是一个n次循环, 最终时间复杂度是O(n^2), 空间复杂度是O(n)

3. 复杂度

• 时间复杂度 O(n^2)
• 空间复杂度 O(n)

3. 代码

# coding:utf8


class Solution:
    def minCut(self, s: str) -> int:
        size = len(s)
        dp = [[False] * size for _ in range(size)]
        min_cut_times = None

        def dfs(s, start, size, dp, cut_times):
            nonlocal min_cut_times
            if start == size:
                if min_cut_times is None or min_cut_times > cut_times - 1:
                    min_cut_times = cut_times - 1
            else:
                for i in range(start, size):
                    if s[i] != s[start]:
                        continue
                    if i - 1 > start + 1 and not dp[i - 1][start + 1]:
                        continue
                    dp[i][start] = True
                    dfs(s, i + 1, size, dp, cut_times + 1)

        dfs(s, 0, size, dp, 0)
        return min_cut_times


def my_test(solution, s):
    print('input: s={}; output: {}'.format(s, solution.minCut(s)))


solution = Solution()
my_test(solution, 'aab')
my_test(solution, 'bb')

输出结果

input: s=aab; output: 1
input: s=bb; output: 0

4. 结果

image.png