Palindrome Partitioning II

  • tags: [DP_Sequence]

Question

  1. Given a string s, cut s into some substrings such that
  2. every substring is a palindrome.
  4. Return the minimum cuts needed for a palindrome partitioning of s.
  6. Example
  7. For example, given s = "aab",
  9. Return 1 since the palindrome partitioning ["aa","b"] could be produced
  10. 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. class Solution:
  2.     # @param s, a string
  3.     # @return an integer
  4.     def minCut(self, s):
  5.         if not s:
  6.             print 0
  8.         cut = [i - 1 for i in xrange(1 + len(s))]
  10.         for i in xrange(1 + len(s)):
  11.             for j in xrange(i):
  12.                 # s[j:i] is palindrome
  13.                 if s[j:i] == s[j:i][::-1]:
  14.                     cut[i] = min(cut[i], 1 + cut[j])
  15.         return cut[-1]

源码分析

  1. 当 s 为 None 或者列表为空时返回0
  2. 初始化切割数数组
  3. 子字符串的索引位置可为[0, len(s) - 1], 内循环 j 比外循环 i 小，故可将 i 的最大值设为1 + len(s) 较为便利。
  4. 回文的判断使用了[::-1] 对字符串进行反转
  5. 最后返回数组最后一个元素

复杂度分析

两重循环，遍历的总次数为 1/2 \cdots n^2), 每次回文的判断时间复杂度为 O(len(s)), 故总的时间复杂度近似为 O(n^3). 在 s 长度较长时会 TLE.
使用了与 s 等长的辅助切割数数组，空间复杂度近似为 O(n).

题解2 - 使用动态规划计算子字符串回文状态

切割数部分使用的是动态规划，优化的空间不大，仔细瞅瞅可以发现在判断字符串是否为回文的部分存在大量重叠计算，故可引入动态规划进行优化，时间复杂度可优化至到平方级别。

定义状态 PaMat[i][j] 为区间 [i,j] 是否为回文的标志, 对应此状态的子问题可从回文的定义出发，如果字符串首尾字符相同且在去掉字符串首尾字符后字符串仍为回文，则原字符串为回文，相应的状态转移方程 PaMat[i][j] = s[i] == s[j] && PaMat[i+1][j-1], 由于状态转移方程中依赖比i大的结果，故实现中需要从索引大的往索引小的递推，另外还需要考虑一些边界条件和初始化方式，做到 bug-free 需要点时间。

Python

  1. class Solution:
  2.     # @param s, a string
  3.     # @return an integer
  4.     def minCut(self, s):
  5.         if not s:
  6.             print 0
  8.         cut = [i - 1 for i in xrange(1 + len(s))]
  9.         PaMatrix = self.getMat(s)
  11.         for i in xrange(1 + len(s)):
  12.             for j in xrange(i):
  13.                 if PaMatrix[j][i - 1]:
  14.                     cut[i] = min(cut[i], cut[j] + 1)
  15.         return cut[-1]
  17.     def getMat(self, s):
  18.         PaMat = [[True for i in xrange(len(s))] for j in xrange(len(s))]
  19.         for i in xrange(len(s), -1, -1):
  20.             for j in xrange(i, len(s)):
  21.                 if j == i:
  22.                     PaMat[i][j] = True
  23.         # not necessary if init with True
  24.                 # elif j == i + 1:
  25.                 #     PaMat[i][j] = s[i] == s[j]
  26.                 else:
  27.                     PaMat[i][j] = s[i] == s[j] and PaMat[i + 1][j - 1]
  28.         return PaMat

C++

  1. class Solution {
  2. public:
  3.     int minCut(string s) {
  4.         if (s.empty()) return 0;
  6.         int len = s.size();
  7.         vector<int> cut;
  8.         for (int i = 0; i < 1 + len; ++i) {
  9.             cut.push_back(i - 1);
  10.         }
  11.         vector<vector<bool> > mat = getMat(s);
  13.         for (int i = 1; i < 1 + len; ++i) {
  14.             for (int j = 0; j < i; ++j) {
  15.                 if (mat[j][i - 1]) {
  16.                     cut[i] = min(cut[i], 1 + cut[j]);
  17.                 }
  18.             }
  19.         }
  21.         return cut[len];
  22.     }
  24.     vector<vector<bool> > getMat(string s) {
  25.         int len = s.size();
  26.         vector<vector<bool> > mat = vector<vector<bool> >(len, vector<bool>(len, true));
  27.         for (int i = len; i >= 0; --i) {
  28.             for (int j = i; j < len; ++j) {
  29.                 if (j == i) {
  30.                     mat[i][j] = true;
  31.                 } else if (j == i + 1) {
  32.                     mat[i][j] = (s[i] == s[j]);
  33.                 } else {
  34.                     mat[i][j] = ((s[i] == s[j]) && mat[i + 1][j - 1]);
  35.                 }
  36.             }
  37.         }
  39.         return mat;
  40.     }
  41. };

Java

  1. public class Solution {
  2.     public int minCut(String s) {
  3.         if (s == null || s.length() == 0) return 0;
  5.         int len = s.length();
  6.         int[] cut = new int[1 + len];
  7.         for (int i = 0; i < 1 + len; ++i) {
  8.             cut[i] = i - 1;
  9.         }
  10.         boolean[][] mat = paMat(s);
  12.         for (int i = 1; i < 1 + len; i++) {
  13.             for (int j = 0; j < i; j++) {
  14.                 if (mat[j][i - 1]) {
  15.                     cut[i] = Math.min(cut[i], 1 + cut[j]);
  16.                 }
  17.             }
  18.         }
  20.         return cut[len];
  21.     }
  23.     private boolean[][] paMat(String s) {
  24.         int len = s.length();
  25.         boolean[][] mat = new boolean[len][len];
  27.         for (int i = len - 1; i >= 0; i--) {
  28.             for (int j = i; j < len; j++) {
  29.                 if (j == i) {
  30.                     mat[i][j] = true;
  31.                 } else if (j == i + 1) {
  32.                     mat[i][j] = (s.charAt(i) == s.charAt(j));
  33.                 } else {
  34.                     mat[i][j] = (s.charAt(i) == s.charAt(j)) && mat[i + 1][j - 1];
  35.                 }
  36.             }
  37.         }
  39.         return mat;
  40.     }
  41. }

源码分析

初始化 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(n^2), 使用了二维回文矩阵保存记忆化搜索结果，空间复杂度为 O(n^2).

Reference