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: 動態(tài)規(guī)劃
- 基本思路是:
- 先初始化最差情形，即dp[i] = i(i = 0~size-1), 即每個字母都自成一個回文, dp[i]表示從0到i構(gòu)成的字符串劃分為回文最少需要切幾刀
- 再自
i=1開始從左到右依次嘗試以每個字母作為回文的中心點, 對于每個中心點mid, 向左向右盡量擴展到start,end, 每左右各擴展一格, 則更新dp[end] = min(dp[end], 1 + dp[start - 1] if start > 0 else 0), 表示截止到end所需切的最少刀數(shù), 取決于當前是否選擇切這一刀境钟，選擇的依據(jù)，就是能否使得dp[end]變小懒鉴，這是典型的動態(tài)規(guī)范思路瓣履，即選擇驯杜，并評價選擇的結(jié)果優(yōu)劣躬拢。 - 需要注意的是，對于中心點的選擇念秧，有可能是一個淤井，也有可能是2個，比如
abba回文就需要拿中間的bb作為中心點,往左往右可擴展方可, 處理方式即start, end = mid - 1, mid, 它擔負的任務與上一步中一樣摊趾，也是要盡量擴展回文長度, 然后盡量縮小dp[end]的值 - 最終只需要返回
dp[size-1]即可
- 分析:
- 過程中需要嘗試以每個字母作為中心點的情形, 所以有一個n次循環(huán), 對于每個中心點, 又要有左右擴展的嘗試, 極端情況下币狠，比如
aaaaaa的情形，每次左右擴展, 都可能到邊界, 因此也是一個n次循環(huán), 最終時間復雜度是O(n^2), 空間復雜度是O(n)
- 復雜度
- 時間復雜度
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')
輸出結(jié)果
input: s=aab; output: 1
input: s=bb; output: 0
4. 結(jié)果
image.png
