108. Palindrome Partitioning II / 132. Palindrome Partitioning II

• 本题难度: Medium/Hard

• Topic: DP

  Description

  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. 使用DFS超时

import collections
class Solution:"""&＃64;param s: A string&＃64;return: An integer"""#min BFSdef minCut(self, s):# write your code heref &＃61; 0q &＃61; collections.deque([[s,f]])while q:[tmps, f] &＃61; q.popleft()if self.isValid(tmps):return felse:for i in range(len(tmps),0,-1):if self.isValid(tmps[:i]):q.append([tmps[i:],f&＃43;1])return 0def isValid(self, s):return s&＃61;&＃61;s[::-1]# l &＃61; len(s)# for i in range(l//2):# if s[i]!&＃61;s[l-1-i]:# return False# return True

别人的代码

DP

def minCut(self, s):cut &＃61; [x for x in range(-1,len(s))]for i in range(0,len(s)):for j in range(i,len(s)):if s[i:j] &＃61;&＃61; s[j:i:-1]:cut[j&＃43;1] &＃61; min(cut[j&＃43;1],cut[i]&＃43;1)return cut[-1]

思路
我的思路&＃xff1a;
最短->bfs

DP思路&＃xff1a;
某一点&＃xff0c;最短距离等于前面的&＃43;最后一个到他的回文。