LeetCode 之 Palindrome Partitioning II（动态规划）

灰太狼 2022-08-03 08:21 257阅读 0赞

【问题描述】

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.

For example, given s = "aab",

Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

1.【基础知识】

1）substr函数掌握模糊；

2）动规与贪心算法的回顾；

3）树的深搜和广搜的应用能力；

4）fill_n函数。

2.【屌丝代码】

卡壳的地方：

1.剩下一个元素可以不切，直接判定跳出（已解决）；

2.动规，一次循环同时进行前向与后向回文判定，并且采用初次前削判定和初次后削判定（已解决）；

3.贪心，每次都比较，得到当下可以最快回文的长度，只不过未能实现（已解决）；

4.解决了全部短小用例，倒在了代码中那段长不拉几的字符串用例上；

5.屌丝算法思想：

1）前向搜索：

1.1）先检查去掉最后Num个元素是不是回文；

1.1.1）是，则判断余下的是不是回文串——不是则直接进入下一层循环，是则直接跳出循环；

1.1.2）不是，继续循环体；

1.2）检查去掉最前Num个元素是不是回文；

1.2.1）是，则判断余下的是不是回文串——不是则直接进入下一层循环，是则直接跳出循环；

1.2.2）不是，继续循环体；

1.3）Num++

1.4）得到最终count_a;

2）后向搜索：

将1.1与1.2调换执行,得到最终count_b；

3）比较count_a与count_b，返回最小值。

  1. #include <vector>  
  2. #include <iostream>
  3. #include <algorithm> 
  4. #include <vector>
  5. #include <string>
  7. using namespace std; 
  9. class Solution {
  10. public:
  11.     int minCut(string s) 
  12.     {
  13.         int len = s.length();
  14.         if(len<=1||IsPld(s)) 
  15.             return 0;
  17.         int tmp_len(len),cot_a(0),cot_b(0);
  18.         string tmp_str = s;
  20.         /*
  21.         for(i=len-1;i>0;i--) // 切几刀？ 如：0，表示不切，原字符串就是一个回文串
  22.         {
  23.             int *arr = (int*)malloc(sizeof(int)*(i+1));
  24.             arr[0] = 0;
  25.             vector<string> subs;
  26.             for(j=1;j<=i+1;j++) // 循环刀数
  27.                 for(k>arr[j-1];k<) // 每一刀怎么切？ 下刀点
  28.                 // 下一刀要比上一刀大；
  29.                 // 第一刀不能比0小；第一刀不能大于串长减刀数；
  30.                 // 第k刀不能比len-k大；
  31.                 // 最后一刀不能比串长大；
  32.                 {
  33.                     s.substr
  34.                 }
  35.             delete []arr;
  36.         }*/
  38.         /*
  39.         while(tmp_len)
  40.         {
  41.             if(IsPld(tmp_str.substr(0,tmp_len)))
  42.             {
  43.                 cot_a++;
  44.                 tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
  45.                 tmp_len = tmp_str.size();
  46.                 if(IsPld(tmp_str))
  47.                     break;
  48.             }
  49.             else 
  50.                 if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
  51.                 {
  52.                     cot_a++;
  53.                     tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
  54.                     tmp_len = tmp_str.size();
  55.                     if(IsPld(tmp_str))
  56.                         break;
  57.                 }
  58.                 else
  59.                 {
  60.                     tmp_len--;
  61.                 }
  62.         }
  63.         tmp_len = len;
  64.         tmp_str = s;        
  65.         while(tmp_len)
  66.         {
  67.             if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
  68.             {
  69.                 cot_b++;
  70.                 tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
  71.                 tmp_len = tmp_str.size();
  72.                 if(IsPld(tmp_str))
  73.                     break;
  74.             }
  75.             else 
  76.                 if(IsPld(tmp_str.substr(0,tmp_len)))
  77.                 {
  78.                     cot_b++;
  79.                     tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
  80.                     tmp_len = tmp_str.size();
  81.                     if(IsPld(tmp_str))
  82.                         break;
  83.                 }
  84.                 else
  85.                 {
  86.                     tmp_len--;
  87.                 }
  88.         }
  89.         return min(cot_a,cot_b);
  90.         */
  91.         while(tmp_len)
  92.         {
  93.             if(IsPld(tmp_str.substr(0,tmp_len)))
  94.             {
  95.                 cot_a++;
  96.                 tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
  97.                 tmp_len = tmp_str.size();
  98.                 if(IsPld(tmp_str))
  99.                     break;
  100.             }
  101.             if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
  102.             {
  103.                 cot_a++;
  104.                 tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
  105.                 tmp_len = tmp_str.size();
  106.                 if(IsPld(tmp_str))
  107.                     break;
  108.             }
  109.                 tmp_len--;
  110.         }
  111.         tmp_len = len;
  112.         tmp_str = s;
  113.         while(tmp_len)
  114.         {
  115.             if(IsPld(tmp_str.substr(tmp_str.size()-tmp_len,tmp_len)))
  116.             {
  117.                 cot_b++;
  118.                 tmp_str = tmp_str.substr(0,tmp_str.size()-tmp_len);
  119.                 tmp_len = tmp_str.size();
  120.                 if(IsPld(tmp_str))
  121.                     break;
  122.                 continue;
  123.             }
  124.             if(IsPld(tmp_str.substr(0,tmp_len)))
  125.             {
  126.                 cot_b++;
  127.                 tmp_str = tmp_str.substr(tmp_len,tmp_str.size()-tmp_len);
  128.                 tmp_len = tmp_str.size();
  129.                 if(IsPld(tmp_str))
  130.                     break;
  131.                 continue;
  132.             }
  133.             tmp_len--;
  134.         }
  135.         return min(cot_b,cot_a);
  136.     }
  137.     bool IsPld(string s)
  138.     {
  139.         if(s.length()<=1)
  140.             return true;
  141.         int i(0),j(s.size()-1);
  142.         while(i<j)
  143.         {
  144.             if(s[i]!=s[j])
  145.                 return false;
  146.             i++;
  147.             j--;
  148.         }
  149.         return true;
  150.     }
  151. };
  153. int main()  
  154. {
  155.     string mystr = "adabdcaebdcebdcacaaaadbbcadabcbeabaadcbcaaddebdbddcbdacdbbaedbdaaecabdceddccbdeeddccdaabbabbdedaaabcdadbdabeacbeadbaddcbaacdbabcccbaceedbcccedbeecbccaecadccbdbdccbcbaacccbddcccbaedbacdbcaccdcaadcbaebebcceabbdcdeaabdbabadeaaaaedbdbcebcbddebccacacddebecabccbbdcbecbaeedcdacdcbdbebbacddddaabaedabbaaabaddcdaadcccdeebcabacdadbaacdccbeceddeebbbdbaaaaabaeecccaebdeabddacbedededebdebabdbcbdcbadbeeceecdcdbbdcbdbeeebcdcabdeeacabdeaedebbcaacdadaecbccbededceceabdcabdeabbcdecdedadcaebaababeedcaacdbdacbccdbcece";
  156.     cout<<mystr.substr(1,2)<<endl; // string.substr(首元素索引，子串长度)
  157.     Solution mySln;
  158.     int num = mySln.minCut(mystr);
  159.     cout<<num<<endl;
  160.     while(1);
  161.     return 0; 
  162. }

3.【源码AC】

  1. // LeetCode, Palindrome Partitioning II
  2. // 时间复杂度 O(n^2)，空间复杂度 O(n^2)
  3. class Solution {
  4. public:
  5.     int minCut(string s) {
  6.         const int n = s.size();
  7.         int f[n+1];
  8.         bool p[n][n];
  9.         fill_n(&p[0][0], n * n, false);
  10.         //the worst case is cutting by each char
  11.         for (int i = 0; i <= n; i++)
  12.         f[i] = n - 1 - i; // 最后一个 f[n]=-1
  13.         for (int i = n - 1; i >= 0; i--) {
  14.             for (int j = i; j < n; j++) {
  15.                 if (s[i] == s[j] && (j - i < 2 || p[i + 1][j - 1])) {
  16.                     p[i][j] = true;
  17.                     f[i] = min(f[i], f[j + 1] + 1);
  18.                 }
  19.             }
  20.         }
  21.     return f[0];
  22.     }
  23. };

4.【复盘】

1）卡壳部分

  • 不能解决的原因在于字符串太长，耗时也在1H以上，题目未解出来；
  • 动规的数学式子未能很好定义提炼。

2）AC源码思想——动态规划

定义状态 f(i,j) 表示区间 [i,j] 之间最小的 cut 数，则状态转移方程为
f(i, j) = min {f(i, k) + f(k + 1, j)} , i ≤ k ≤ j,0 ≤ i ≤ j < n
这是一个二维函数，实际写代码比较麻烦。所以要转换成一维 DP。如果每次，从 i 往右扫描，每找到一个回文就算一次 DP 的话，就可以转换为

f(i) = 区间 [i, n-1] 之间最小的 cut 数

n 为字符串长度，则状态转移方程为
f(i) = min {f(j + 1) + 1} , i ≤ j < n
一个问题出现了，就是如何判断 [i,j] 是否是回文？每次都从 i 到 j 比较一遍？太浪费了，这里也是一个 DP 问题。
定义状态 P[i][j] = true if [i,j] 为回文 ，那么

P[i][j] = ( str[i] == str[j] && P[i+1][j-1] )

发表评论

表情：
评论列表 （有 0 条评论，257人围观）

还没有评论，来说两句吧...

相关阅读