[问题描述]
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
原文：http://www.cnblogs.com/taizy/p/4008822.html