Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
Solution1: DP
dp[i] := ans of str[0:i]
dp[j] = { x + str[i:len] for x in dp[i] }, 0 <= i < len
Time complexity: O(2^n)
Space complexity: O(2^n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua bool isPalindrome(const string& s) { const int n = s.length(); for (int i = 0; i < n / 2; ++i) if (s[i] != s[n - 1 - i]) return false; return true; } class Solution { public: vector<vector<string>> partition(string s) { int n = s.length(); vector<vector<vector<string>>> dp(n + 1); for (int len = 1; len <= n; ++len) { for (int i = 0; i < len; ++i) { string right = s.substr(i, len - i); if (!isPalindrome(right)) continue; if (i == 0) dp[len].push_back({right}); for (const auto& p : dp[i]) { dp[len].push_back(p); dp[len].back().push_back(right); } } } return dp[n]; } }; |
Solution 2: DFS
Time complexity: O(2^n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua bool isPalindrome(const string& s, int l, int r) { while (l < r) if (s[l++] != s[r--]) return false; return true; } class Solution { public: vector<vector<string>> partition(string s) { int n = s.length(); vector<vector<string>> ans; vector<string> cur; function<void(int)> dfs = [&](int start) { if (start == n) { ans.push_back(cur); return; } for (int i = start; i < n; ++i) { if (!isPalindrome(s, start, i)) continue; cur.push_back(s.substr(start, i - start + 1)); dfs(i + 1); cur.pop_back(); } }; dfs(0); return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment