首页 > 代码库 > LeetCode: Palindrome Partition
LeetCode: Palindrome Partition
LeetCode: Palindrome Partition
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"] ]
地址：https://oj.leetcode.com/problems/palindrome-partitioning/
算法：可以用动态规划来解决。用一个二维数组dp来存储所有子问题的解，一维数组dp[i]用来存储0～i的字串的所有解，其中每个解用最后一个回文开始位置来标记。比如对于上面的字符串“aab”，
dp[0]={0},dp[1]={0,1},dp[2]={2}。这样，在构造解的过程中就可以采用递归的方法，对dp[n-1]中的所有值dp[n-1][j]先递归构造出字串0～dp[n-1][j]-1，然后在加上dp[n-1][j]~n-1
字串。具体代码：
1 class Solution { 2 public: 3 vector<vector<string> > partition(string s) { 4 int n = s.size(); 5 if (n < 1) return vector<vector<string> >(); 6 vector<vector<int> > dp(n); 7 dp[0].push_back(0); 8 for (int i = 1; i < n; ++i){ 9 if(isPalindrome(s.substr(0,i+1))){10 dp[i].push_back(0);11 }12 dp[i].push_back(i);13 for (int j = i-2; j >= 0; --j){14 if(isPalindrome(s.substr(j+1,i-j))){15 dp[i].push_back(j+1);16 }17 }18 }19 return constructResult(s,dp,n);20 }21 bool isPalindrome(const string &s){22 int len = s.size();23 int n = len / 2;24 int i = 0;25 while(i < n && s[i] == s[len-1-i]) ++i;26 return i == n;27 }28 vector<vector<string> > constructResult(string &s, vector<vector<int> > &dp,int n){29 if (n < 1){30 return vector<vector<string> >();31 }32 vector<int>::iterator it = dp[n-1].begin();33 vector<vector<string> > result;34 for (; it != dp[n-1].end(); ++it){35 if (*it == 0){36 vector<string> temp1;37 temp1.push_back(s.substr(0,n));38 result.push_back(temp1);39 continue;40 }41 vector<vector<string> >temp2 = constructResult(s,dp,*it);42 vector<vector<string> >::iterator str_it = temp2.begin();43 for(; str_it != temp2.end(); ++str_it){44 str_it->push_back(s.substr(*it,n-(*it)));45 result.push_back(*str_it);46 }47 }48 return result;49 }50 };第二题：
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.
地址：https://oj.leetcode.com/problems/palindrome-partitioning-ii/
算法：同样用动态规划来解决，但这次只要用一维数组dp来储存所有子问题。其中dp[i]表示字串0～i所用的最小cut，dp[i+1]=min{dp[j-1] | 0 =< j <= i+1 且 字串j~i+1是回文}。代码：
1 class Solution { 2 public: 3 int minCut(string s) { 4 int n = s.size(); 5 if(n < 1) return 0; 6 vector<int> dp(n); 7 dp[0] = 0; 8 for(int i = 1; i < n; ++i){ 9 if(isPalindrome(s.substr(0,i+1))){10 dp[i] = 0;11 continue;12 }13 int min_value =http://www.mamicode.com/ n;14 for(int j = i-1; j >= 0; --j){15 if(dp[j]+1 < min_value){16 if(isPalindrome(s.substr(j+1,i-j))){17 min_value = http://www.mamicode.com/dp[j] + 1;18 }19 }20 }21 dp[i] = min_value;22 }23 return dp[n-1];24 }25 bool isPalindrome(const string &s){26 int len = s.size();27 int n = len / 2;28 int i = 0;29 while(i < n && s[i] == s[len-1-i]) ++i;30 return i == n;31 }32 };
LeetCode: Palindrome Partition
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。