首页 > 代码库 > 回文分割
回文分割
周末女朋友不在家，打算做几题LeetCode的题目练练手，Pick One，随机抽中Palindrome Partitioning，题目如下：
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
思路很简单，构建子串的树，用回溯法，遍历每个子串，若当前子串是回文，则递归遍历子节点
Talk is cheap，show me the code.
1 class Solution { 2 public: 3 vector<vector<string>> partition(string s) { 4 vector<vector<string>> all_answer; 5 vector<string> answer; 6 backtracking(s, 0, all_answer, answer); 7 return all_answer; 8 } 9 void print(vector<vector<string>> all_answer)10 {11 for (auto it = all_answer.begin(); it != all_answer.end(); it++)12 {13 for (auto it2 = it->begin(); it2 != it->end(); it2++)14 {15 cout << *it2 << " ";16 }17 cout << endl;18 }19 }20 private:21 bool is_palindrome(string s)22 {23 unsigned int i = 0;24 string::iterator it = s.begin();25 string::reverse_iterator it2 = s.rbegin();26 while (i < s.length()/2 && it != s.end())27 {28 if (*it != *it2)29 {30 return false;31 }32 ++i;33 ++it;34 ++it2;35 }36 return true;37 }38 void backtracking(string s, unsigned int current, vector<vector<string>> &all_answer, vector<string> &answer)39 {40 if (current == s.length())41 {42 all_answer.push_back(answer);43 return;44 }45 else46 {47 for (unsigned int i = 1; i <= s.length()-current; ++i)48 {49 string current_str = s.substr(current, i);50 if (is_palindrome(current_str))51 {52 answer.push_back(current_str);53 backtracking(s, current+i, all_answer, answer);54 answer.pop_back(); //backtracking55 }56 }57 }58 }59 };
提交，显示Accepted。看到问题列表中还有Palindrome Partitioning II，就想一鼓作气做完。题目如下：
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 palindromepartitioning ["aa","b"] could be produced using 1 cut.
乍一看比第一题还简单，但是明显测试用例会对时间复杂度做更高的要求，果然，直接改用第一题的方法，显示Time Limit Exceeded，通不过的测试用例是：
"fifgbeajcacehiicccfecbfhhgfiiecdcjjffbghdidbhbdbfbfjccgbbdcjheccfbhafehieabbdfeigbiaggchaeghaijfbjhi"
这个字符串长度100，于是修改算法，观察上一张图，分割的次数其实就是树的层级，之前用的回溯法是深度遍历，如果只需要最小的分割次数，那么只需要按层级遍历，找到一种分割即可返回。利用队列实现层级遍历，修改代码如下：
1 class Solution { 2 public: 3 int minCut_1(string s) { 4 queue<node> node_queue; 5 unsigned int current = 0; 6 node first_node = {0, 0, 0}; 7 node_queue.push(first_node); 8 while(node_queue.size()) 9 {10 node current_check = node_queue.front();11 node_queue.pop();12 string current_substr = s.substr(current_check.curret_position, current_check.sub);13 if (is_palindrome(current_substr))14 {15 unsigned int new_current = current_check.curret_position+current_check.sub;16 if (new_current == s.length())17 {18 return current_check.layer;19 }20 else21 {22 for (unsigned int i = s.length()-new_current; i >= 1; --i)23 {24 node sub_node = {new_current, i, current_check.layer+1};25 node_queue.push(sub_node);26 }27 }28 }29 }30 return -1;31 }32 33 private:34 struct node35 {36 unsigned int curret_position;37 unsigned int sub;38 int layer;39 };40 bool is_palindrome(string s)41 {42 unsigned int i = 0;43 string::iterator it = s.begin();44 string::reverse_iterator it2 = s.rbegin();45 while (i < s.length()/2 && it != s.end())46 {47 if (*it != *it2)48 {49 return false;50 }51 ++i;52 ++it;53 ++it2;54 }55 return true;56 }57 };
但是这样仍然显示Time Limit Exceeded，因为在最坏情况下，这个算法还是要遍历大多数层级，而这个测试用例就是很少回文的情况。跑到41层的时候队列长度就已经超过100万了
思考一下，我们需要的只是最小的分割次数，但是我之前的思路总是离不开树的遍历，其实是获取了具体的分割结果，付出极大的计算代价。类似之前做过的解一道题（两篇博客居然相隔两年，汗）只聚焦于分割次数，可以改用动态规划来做：
令d[i]为s[0…i]的最小分割次数，s[0…i]可分割为s[0…j]和s[j+1…i]，若s[j+1…i]是回文，则d[i] = min(d[j]+1,d[i]).修改后代码如下：
class Solution {public: int minCut_2(string s) { vector<int> dp; for (unsigned int i = 1; i <= s.length();++i) { if (is_palindrome(s.substr(0, i))) { dp.push_back(0); continue; } else { dp.push_back(i-1); } for (unsigned int j = 1; j < i; j++) { string current_substr = s.substr(j, i-j); if (is_palindrome(current_substr)) { if (dp[i-1] > dp[j-1]+1) { dp[i-1] = dp[j-1]+1; } } } } return dp[s.length()-1]; }private: bool is_palindrome(string s) { unsigned int i = 0; string::iterator it = s.begin(); string::reverse_iterator it2 = s.rbegin(); while (i < s.length()/2 && it != s.end()) { if (*it != *it2) { return false; } ++i; ++it; ++it2; } return true; }};
但是还是Time Limit Exceeded，但是这次通不过的测试用例是：
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
字符串长度1462，搞不定，没思路了，看discussion里别人的方法，原来是不仅最小分割数做了动态规划，子串的回文判断也用了动态规划：
用pal[i][j]记录子串s[i..j]是否是回文，根据pal[j+1][i-1]与s[i]==s[j]判断pal[j][i]是否是回文。修改代码如下：
class Solution {public: int minCut(string s) { if(s.empty()) return 0; int n = s.length(); vector<vector<bool>> pal(n,vector<bool>(n,false)); vector<int> dp(n); for (int i = 0; i < n;++i) { dp[i] = i>1 ? dp[i-1]+1 : i; pal[i][i] = true; for (int j = 0; j < i; j++) { if(s[i]==s[j] && (i-j<2 || pal[j+1][i-1])) { pal[j][i]=true; if (0 == j) { dp[i] = 0; } else if (dp[j-1]+1 < dp[i]) { dp[i] = dp[j-1]+1; } } } } return dp[n-1]; }};
提交后终于Accepted，耗时244ms。
做这题花费了一天时间，把树的遍历和动态规划也都再复习了一遍，获益匪浅。