[C++]LeetCode: 121 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"] ]
思路:我们需要将一个字符串分割成回文子串的形式,然后返回所有的分割结果。需要两个辅助函数,一个是递归的DFS,帮助我们分割字符串,可以借鉴Restore IP Addresses的分割思想,我们循环所有的分割长度,从1开始直到剩余子串的长度(注意可以取等号i = s.size()),然后判断这个子串是否是回文,可以借鉴Valid Palindrome 中的方法,我们设置两个坐标从头尾判断,同时移动,如果有不相等返回false. 如果这个子串是回文,添加到tmp结果中,将剩余的字符串传给helper函数继续递归,直到剩余子串为空时,返回结果。重要的是,我们需要维护现场,将添加进去的子串结果pop_back出来。这样保证下次选择不同长度时,没有重复字符在结果中。
Attention:
1. 迭代终止条件,剩余子串长度为0.
if(s.size() == 0) { ret.push_back(tmp); return; }2. 每次选择剩余子串进行递归。递归结束后,要维护现场。
int strlen = s.size(); tmp.push_back(substr); partition_helper(s.substr(i, strlen - i), tmp, ret); tmp.pop_back();3. i代表分割子串的长度,不是坐标,所以长度可以取字符串的长度。注意取等号。
for(int i = 1; i <= s.size(); i++)
复杂度:取决于结果的数量,最坏情况是指数量级的。
AC Code:
class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> ret; if(s.size() == 0) return ret; vector<string> tmp; partition_helper(s, tmp, ret); return ret; } private: void partition_helper(string s, vector<string> tmp, vector<vector<string>>& ret) { if(s.size() == 0) { ret.push_back(tmp); return; } for(int i = 1; i <= s.size(); i++) { string substr = s.substr(0, i); if(isPalindrome(substr)) { int strlen = s.size(); tmp.push_back(substr); partition_helper(s.substr(i, strlen - i), tmp, ret); tmp.pop_back(); } } } //假设不含空格等其他字符,只含小写字母 bool isPalindrome(string s) { int len = s.size(); if(len == 0 || len == 1) return true; int i = 0; int j = len - 1; while(i < j) { if(s[i++] != s[j--]) { return false; } } return true; } };
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。