# Palindrome Partitioning II - tags: [[DP_Sequence](# "單序列動態規劃，通常使用 f[i] 表示前i個位置/數字/字母... 使用 f[n-1] 表示最后返回結果。")] ### Source - leetcode: [Palindrome Partitioning II | LeetCode OJ](https://leetcode.com/problems/palindrome-partitioning-ii/) - lintcode: [(108) Palindrome Partitioning II](http://www.lintcode.com/en/problem/palindrome-partitioning-ii/) ~~~ 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 ~~~ class Solution: # @param s, a string # @return an integer def minCut(self, s): if not s: print 0 cut = [i - 1 for 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] ~~~ ### 源碼分析 1. 當 s 為 None 或者列表為空時返回0 1. 初始化切割數數組 1. 子字符串的索引位置可為`[0, len(s) - 1]`, 內循環 j 比外循環 i 小，故可將 i 的最大值設為`1 + len(s)` 較為便利。 1. 回文的判斷使用了`[::-1]` 對字符串進行反轉 1. 最后返回數組最后一個元素 ### 復雜度分析 兩重循環，遍歷的總次數為 1/2?n2)1/2 \cdots n^2)1/2?n2), 每次回文的判斷時間復雜度為 O(len(s))O(len(s))O(len(s)), 故總的時間復雜度近似為 O(n3)O(n^3)O(n3). 在 s 長度較長時會 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。").使用了與 s 等長的輔助切割數數組，空間復雜度近似為 O(n)O(n)O(n). ### 題解2 - 使用動態規劃計算子字符串回文狀態 切割數部分使用的是動態規劃，優化的空間不大，仔細瞅瞅可以發現在判斷字符串是否為回文的部分存在大量重疊計算，故可引入動態規劃進行優化，時間復雜度可優化至到平方級別。 定義狀態 PaMat[i][j] 為區間 `[i,j]` 是否為回文的標志, 對應此狀態的子問題可從回文的定義出發，如果字符串首尾字符相同且在去掉字符串首尾字符后字符串仍為回文，則原字符串為回文，相應的狀態轉移方程 `PaMat[i][j] = s[i] == s[j] && PaMat[i+1][j-1]`, 由于狀態轉移方程中依賴比`i`大的結果，故實現中需要從索引大的往索引小的遞推，另外還需要考慮一些邊界條件和初始化方式，做到 bug-free 需要點時間。 ### Python ~~~ class Solution: # @param s, a string # @return an integer def minCut(self, s): if not s: print 0 cut = [i - 1 for 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] def getMat(self, s): PaMat = [[True for 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 ~~~ ### C++ ~~~ class Solution { public: int minCut(string s) { if (s.empty()) return 0; int len = s.size(); vector<int> cut; for (int i = 0; i < 1 + len; ++i) { cut.push_back(i - 1); } vector<vector<bool> > mat = getMat(s); for (int i = 1; i < 1 + len; ++i) { for (int j = 0; j < i; ++j) { if (mat[j][i - 1]) { cut[i] = min(cut[i], 1 + cut[j]); } } } return cut[len]; } vector<vector<bool> > getMat(string s) { int len = s.size(); vector<vector<bool> > mat = vector<vector<bool> >(len, vector<bool>(len, true)); for (int i = len; i >= 0; --i) { for (int j = i; j < len; ++j) { if (j == i) { mat[i][j] = true; } else if (j == i + 1) { mat[i][j] = (s[i] == s[j]); } else { mat[i][j] = ((s[i] == s[j]) && mat[i + 1][j - 1]); } } } return mat; } }; ~~~ ### Java ~~~ public class Solution { public int minCut(String s) { if (s == null || s.length() == 0) return 0; int len = s.length(); int[] cut = new int[1 + len]; for (int i = 0; i < 1 + len; ++i) { cut[i] = i - 1; } boolean[][] mat = paMat(s); for (int i = 1; i < 1 + len; i++) { for (int j = 0; j < i; j++) { if (mat[j][i - 1]) { cut[i] = Math.min(cut[i], 1 + cut[j]); } } } return cut[len]; } private boolean[][] paMat(String s) { int len = s.length(); boolean[][] mat = new boolean[len][len]; for (int i = len - 1; i >= 0; i--) { for (int j = i; j < len; j++) { if (j == i) { mat[i][j] = true; } else if (j == i + 1) { mat[i][j] = (s.charAt(i) == s.charAt(j)); } else { mat[i][j] = (s.charAt(i) == s.charAt(j)) && mat[i + 1][j - 1]; } } } return mat; } } ~~~ ### 源碼分析 初始化 cut 長度為`1 + len(s)`, `cut[0] = -1` 便于狀態轉移方程實現。在執行`mat[i][j] == ... mat[i + 1][j - 1]`時前提是`j - 1 > i + 1`, 所以才需要分情況賦值。使用`getMat` 得到字符串區間的回文矩陣，由于cut 的長度為1+len(s), 兩重 for 循環時需要注意索引的取值，這個地方非常容易錯。 ### 復雜度分析 最壞情況下每次 for 循環都遍歷 n 次，時間復雜度近似為 O(n2)O(n^2)O(n2), 使用了二維回文矩陣保存記憶化搜索結果，空間復雜度為 O(n2)O(n^2)O(n2). ### Reference - [Palindrome Partitioning II 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/palindrome-partitioning-ii/) - soulmachine 的 leetcode 題解