Given a string s, cut s into some substrings such that every substring is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
题解1 - 仅对最小切割数使用动态规划
此题为难题,费了我九牛二虎之力才bug-free :( 求最小切分数,非常明显的动规暗示。由问题出发可建立状态f[i] 表示到索引i 处时需要的最少切割数(即切割前 i 个字符组成的字符串),状态转移方程为f[i] = min{1 + f[j]}, where j < i and substring [j, i] is palindrome, 判断区间[j, i] 是否为回文简单的方法可反转后比较。
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution: # @param s, a string # @return an integer defminCut(self, s): ifnot s: print0
cut = [i - 1for i in xrange(1 + len(s))]
for i in xrange(1 + len(s)): for j in xrange(i): # s[j:i] is palindrome if s[j:i] == s[j:i][::-1]: cut[i] = min(cut[i], 1 + cut[j]) return cut[-1]
源码分析
当 s 为 None 或者列表为空时返回0
初始化切割数数组
子字符串的索引位置可为[0, len(s) - 1], 内循环 j 比外循环 i 小,故可将 i 的最大值设为1 + len(s) 较为便利。
回文的判断使用了[::-1] 对字符串进行反转
最后返回数组最后一个元素
复杂度分析
两重循环,遍历的总次数为 \[1/2 \cdots n^2)\], 每次回文的判断时间复杂度为 \[O(len(s))\], 故总的时间复杂度近似为 \[O(n^3)\]. 在 s 长度较长时会 TLE. 使用了与 s 等长的辅助切割数数组,空间复杂度近似为 \[O(n)\].
classSolution: # @param s, a string # @return an integer defminCut(self, s): ifnot s: print0
cut = [i - 1for i in xrange(1 + len(s))] PaMatrix = self.getMat(s)
for i in xrange(1 + len(s)): for j in xrange(i): if PaMatrix[j][i - 1]: cut[i] = min(cut[i], cut[j] + 1) return cut[-1]
defgetMat(self, s): PaMat = [[Truefor i in xrange(len(s))] for j in xrange(len(s))] for i in xrange(len(s), -1, -1): for j in xrange(i, len(s)): if j == i: PaMat[i][j] = True # not necessary if init with True # elif j == i + 1: # PaMat[i][j] = s[i] == s[j] else: PaMat[i][j] = s[i] == s[j] and PaMat[i + 1][j - 1] return PaMat