首页 > 代码库 > leetcode -- Palindrome Partitioning
leetcode -- 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"] ]
[解题思路]
动态规划，dp[i][j] = s[i]==s[j]&&(j-i<2||dp[i+1][j-1])
1 vector<vector<string>> Solution::partition(string s){ 2 const int len = s.length(); 3 bool dp[len][len]; 4 fill_n(&dp[0][0], len*len, false); 5 for (int i = len-1; i >=0; i --){ 6 for (int j = i; j < len; j++){ 7 dp[i][j] = s[i]==s[j]&&(j-i<2||dp[i+1][j-1]); 8 } 9 }10 vector<vector<string>> ans[len];11 for (int i = len-1; i>=0; i--){12 for (int j = i; j < len; j++){13 if (dp[i][j] == 1){14 const string tmp = s.substr(i, j-i+1);15 if (j + 1 >= len){16 ans[i].push_back(vector<string> {tmp});17 }18 else{19 for (auto k : ans[j + 1]){20 k.insert(k.begin(), tmp);21 ans[i].push_back(k);22 }23 }24 }25 }26 }27 return ans[0];28 }
leetcode -- Palindrome Partitioning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。