Palindrome Partitioning I

第一种方法是DFS，将所有可能的前缀找到，递归调用partition(剩余字符串)

复杂度为O(2^n)

代码如下：

    vector
  
   > partition(string s) {
        vector
   
    > res; vector
    
      patition; if (s.size() == 0) return res; partition(s, patition, res); return res; } void partition(string s, vector
     
      & patition, vector
      
       >& res) { for (int i = 1; i < s.size(); i++) { if (isPalindrome(s.substr(0, i))) { patition.push_back(s.substr(0, i)); partition(s.substr(i), patition, res); patition.pop_back(); } } if (isPalindrome(s)) { patition.push_back(s); res.push_back(patition); patition.pop_back(); } } bool isPalindrome(string s) { int l = 0, r = s.size() - 1; while (l <= r) { if (s[l] != s[r]) return false; l++; r--; } return true; }
      
     
    
   
  

来自 https://oj.leetcode.com/discuss/9623/my-java-dp-only-solution-without-recursion-o-n-2

res(i)表示s[0...i-1]的所有分解方式

isPalin(i,j)表示s[i...j]是否为回文串

isPalin(i,j) = true if i==j or (s[i] == s[j] and isPalin(i + 1, j - 1)) or (s[i] == s[j] and i + 1 == j)

res(i) = res(j) + s[j...i-1] if isPalin(j, i-1)

    vector
  
   > partition(string s) {
        int size = s.size();
        vector
   
    >> res(size + 1); res[0].push_back(vector
    
     (0)); vector
     
      > isPalin(size + 1, vector
      
       (size + 1, false)); for (int i = 0; i < size; i++) { for (int j = 0; j <= i; j++) { if (i == j || s[i] == s[j] && (j + 1 == i || isPalin[j + 1][i - 1])) { isPalin[j][i] = true; for (int p = 0; p < res[j].size(); p++) { vector
       
         prefix = res[j][p]; prefix.push_back(s.substr(j, i - j + 1)); res[i + 1].push_back(prefix); } } } } return res[size]; }
       
      
     
    
   
  

Palindrome Partitioning II

按照Palindrome Partitioning I的DP的代码，不难得到。

代码如下：

   int minCut(string s) {
        int size = s.size();
        vector
  
    cut(size + 1, INT_MAX);
        vector
   
    > isPalin(size + 1, vector
    
     (size + 1, false)); cut[0] = 0; for (int i = 0; i < size; i++) { for (int j = 0; j <= i; j++) { if (i == j || s[i] == s[j] && (j + 1 == i || isPalin[j + 1][i - 1])) { isPalin[j][i] = true; cut[i + 1] = min(cut[i + 1], cut[j] + 1); } } } return cut[size] - 1; }
    
   
  

第二种方法省去了isPalin数组

来自https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

对于s中的位置i，分别寻找以i为中心的奇数长度回文子串s[i-j...i+j] 和偶数长度回文子串s[i-j+1...i+j]

从而有cut(i + j + 1) = min{cut(i - j) + 1, cut(i - j + 1) + 1}

代码如下：

   int minCut(string s) {
        int n = s.size();
        vector
  
    cut(n+1, 0);  // number of cuts for the first k characters
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

            for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
        }
        return cut[n];
    }