首页 > 代码库 > leetcode -- Palindrome Partitioning

leetcode -- Palindrome Partitioning

2024-07-25 19:46:42   217人阅读

 

谋事在人，成事在天

 

[问题描述]

 

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


联系
我们