首页 > 代码库 > Palindrome Partitioning系列
Palindrome Partitioning系列
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"] ]
方法一：暴力破解，直接深度搜索字串，直到找到所有解为止。假设字符串为S=a0a1a2a3a4a5...an，那么从下标0开始往后找回文字串，假设下标为i时有S[0...i]是回文，则将原问题化为子问题，即在S[i+1...n]中继续从头往后寻找回文字串，详细请看代码：
1 class Solution { 2 public: 3 vector<vector<string>> partition(string s) { 4 ans.clear(); 5 vector<string> vstrs; 6 dfs(vstrs, s); 7 return ans; 8 } 9 10 private:11 void dfs(vector<string>& vstrs, string s) { //深度搜索12 if( s.empty() ) { //如果s为空串，则说明前面的切割出的字串均为回文13 ans.push_back(vstrs);14 return ;15 }16 for(int i=1; i<=s.length(); ++i) { //依次从前往后开始切割17 string tstr = s.substr(0, i);18 if( ispalindrome(tstr) ) { //如果被切割出的字符串是回文19 vstrs.push_back(tstr); //存放结果20 dfs(vstrs, s.substr(i, s.length()-i)); //继续深搜未被切割的后面的字串21 vstrs.pop_back(); //pop结果22 }23 }24 }25 26 //判断是否是回文27 bool ispalindrome(const string& s) {28 for(int i=0, j=s.length()-1; i<j; ++i,--j)29 if( s[i] != s[j] ) return false;30 return true;31 }32 33 private:34 vector< vector<string> > ans; //保存切割后的结果35 };
方法二：转为dp问题，另dp[i][j] 以 i 为起点，长度为 j 的的字串，则有
当 s[i] == s[i+j-1] 且 dp[i+1][j-2] == true 时 dp[i][j] = true;否则为false
当 j = 1 时 dp[i][j] = true;
最后通过dp二维数组，依然深度搜索字串，得出最后的结果，代码如下：
1 class Solution { 2 public: 3 vector<vector<string>> partition(string s) { 4 if( s.empty() ) 5 return vector< vector<string> >(); 6 vector< vector<bool> > dp(s.length(), vector<bool>(s.length()+1, false)); //行代表子串起始坐标，列代表字串长度 7 for(int j=0; j<2; ++j) //长度为0,1都认为是回文 8 for(int i=0; i<s.length(); ++i) 9 dp[i][j] = true;10 for(int j=2; j<=s.length(); ++j) //从长度为2开始计算11 for(int i=0; i<=s.length()-j; ++i)12 dp[i][j] = dp[i+1][j-2] && (s[i] == s[i+j-1]);13 ans.clear();14 vector<string> vstrs;15 dfs(dp, vstrs, s, 0, s.length()); //深搜dp，找出满足条件的结果16 return ans;17 }18 19 //k为子串起始下标20 void dfs(vector<vector<bool> >& dp, vector<string>& vstrs, string& s, int k, int n) {21 if( k >= n ) {22 ans.push_back(vstrs);23 return ;24 }25 int len = n-k; //子串[k...n-1]的长度26 for(int i=1; i<=len; ++i) { //长度为1开始遍历27 if( dp[k][i] ) { //如果字串s[k...k+i-1]是回文28 vstrs.push_back(s.substr(k,i));29 dfs(dp, vstrs, s, k+i, n);30 vstrs.pop_back();31 }32 }33 }34 35 private:36 vector< vector<string> > ans; //保存切割后的结果37 };
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 palindrome partitioning ["aa","b"] could be produced using 1 cut.
Palindrome Partitioning系列