Skip to content

Latest commit

 

History

History
125 lines (78 loc) · 3.8 KB

0132._Palindrome_Partitioning_II.md

File metadata and controls

125 lines (78 loc) · 3.8 KB

132. Palindrome Partitioning II

难度: Hard

刷题内容

原题连接

内容描述

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.

解题方案

思路 1 - 时间复杂度: O(N^3)- 空间复杂度: O(N^2)******

  • 我们维护一个一维数组cut，cut[i]代表s[:i+1]最少需要多少次cut
  • 然后我们发现对于j<=i, 如果s[j:i+1]是Palindrome。则cut[i] = min(cut[i], cut[j-1] + 1) if j > 0 else 0， 因为如果j为0的话说明s[:i+1]都是Palindrome了，完全不需要cut，所以当j==0的时候cut[i] = 0
  • 最后返回cut[-1]即可
class Solution:
    def minCut(self, s: str) -> int:
        cut = list(range(len(s)))
        for i in range(len(s)):
            for j in range(i+1):
                if s[j:i+1] == s[j:i+1][::-1]:
                    cut[i] = min(cut[i], cut[j-1] + 1) if j > 0 else 0
        return cut[-1]

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

我们发现每次都要算s[j:i+1]是否为Palindrome太浪费时间了， 用一个dp数组记录一下

  • 我们维护一个二维数组dp，dp[i][j]代表s[i:j+1]是否为Palindrome
  • 然后维护一个一维数组cut，cut[i]代表s[:i+1]最少需要多少次cut
  • 然后我们发现对于j<=i, 如果s[j:i+1]是Palindrome。则cut[i] = min(cut[i], cut[j-1] + 1) if j > 0 else 0， 因为如果j为0的话说明s[:i+1]都是Palindrome了，完全不需要cut，所以当j==0的时候cut[i] = 0
  • 最后返回cut[-1]即可
class Solution:
    def minCut(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        cut = [0] * len(s)
        for i in range(len(s)):
            cut[i] = i
            for j in range(i+1):
                if s[i] == s[j] and (j+1 >= i-1 or dp[j+1][i-1]):
                    dp[j][i] = True
                    cut[i] = min(cut[i], cut[j-1] + 1) if j > 0 else 0
        return cut[-1]

思路 3 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

我们在空间上也可以继续优化

  • 我们维护一个一维数组cut，cut[i] 代表前i个字符最少需要几次cut
  • 然后对于每一个字符s[i]，我们分两种情况讨论
    • 将s[i]作为palindrome的中间字符（odd length），向两边各扩展j个字符，使得s[i-j:i+j+1]是palindrome，同时保证不越界， 此时cut[i+j+1] = min(cut[i+j+1], cut[i-j] + 1)
    • 将s[i]作为palindrome的中间靠前的那个字符（even length），向左边扩展j-1个字符，向右边扩展j个字符，使得s[i-j+1:i+j+1]是palindrome，同时保证不越界， 此时cut[i+j+1] = min(cut[i+j+1], cut[i-j+1] + 1)
  • 最后返回cut[-1]

参考My solution does not need a table for palindrome, is it right ? It uses only O(n) space.

class Solution:
    def minCut(self, s: str) -> int:
        cut = list(range(-1, len(s))) # cut[i] 代表前i个字符最少需要几次cut
        for i in range(len(s)):
            j = 0
            while i - j >= 0 and i + j < len(s) and s[i-j] == s[i+j]: # odd length palindrome
                cut[i+j+1] = min(cut[i+j+1], cut[i-j] + 1)
                j += 1
            j = 1
            while i - j + 1 >= 0 and i + j < len(s) and s[i-j+1] == s[i+j]: # even length palindrome
                cut[i+j+1] = min(cut[i+j+1], cut[i-j+1] + 1)
                j += 1  
        return cut[-1]