Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false.
A string is said to be palindrome if it the same string when reversed.
Example 1:
Input: s = "abcbdd" Output: true Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three substrings are palindromes.
Example 2:
Input: s = "bcbddxy" Output: false Explanation: s cannot be split into 3 palindromes.
Constraints:
3 <= s.length <= 2000s consists only of lowercase English letters.
Solution: DP
dp[i][j] := whether s[i]~s[j] is a palindrome.
dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
ans = any(dp[0][i-1] and dp[i][j] and dp[j][n-1]) for j in range(i, n – 1) for i in range(1, n)
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: bool checkPartitioning(string s) { const int n = s.length(); vector<vector<int>> dp(n, vector<int>(n, 1)); for (int l = 2; l <= n; ++l) for (int i = 0, j = i + l - 1; j < n; ++i, ++j) dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]; for (int i = 1; i < n; ++i) for (int j = i; j + 1 < n; ++j) if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true; return false; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment