diff options
-rw-r--r-- | palindrome_partitioning4.c | 45 | ||||
-rw-r--r-- | palindrome_partitioning4.py | 34 |
2 files changed, 79 insertions, 0 deletions
diff --git a/palindrome_partitioning4.c b/palindrome_partitioning4.c new file mode 100644 index 0000000..4ea0a02 --- /dev/null +++ b/palindrome_partitioning4.c @@ -0,0 +1,45 @@ +// 1745. Palindrome Partitioning IV +#include "leetcode.h" + +/* + * 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 a palindrome if it is the same string when reversed + */ + +bool helper(bool **is_palindrome, int k, int a, int b) { + if (k == 1) + return is_palindrome[a][b]; + for (int i = a; i <= b - (k - 1); i++) + if (is_palindrome[a][i] && helper(is_palindrome, k - 1, i + 1, b)) + return true; + return false; +} + +bool checkPartitioning(char *s) { + int n = strlen(s); + bool **is_palindrome = (bool **)malloc(n * sizeof(bool *)); + for (int i = 0; i < n; i++) + is_palindrome[i] = (bool *)calloc(n, sizeof(bool)); + for (int i = 0; i < n; i++) + is_palindrome[i][i] = true; + for (int i = 0; i < n - 1; i++) + is_palindrome[i][i + 1] = (s[i] == s[i + 1]); + for (int len = 3; len <= n; len++) + for (int i = 0; i <= n - len; i++) { + int j = i + len - 1; + if (s[i] == s[j]) + is_palindrome[i][j] = is_palindrome[i + 1][j - 1]; + } + bool ans = helper(is_palindrome, 3, 0, n - 1); + for (int i = 0; i < n; i++) + free(is_palindrome[i]); + free(is_palindrome); + return ans; +} + +int main() { + char *s1 = "abcbdd", *s2 = "bcbddxy"; + printf("%d\n", checkPartitioning(s1)); // expect: 1 + printf("%d\n", checkPartitioning(s2)); // expect: 0 +} diff --git a/palindrome_partitioning4.py b/palindrome_partitioning4.py new file mode 100644 index 0000000..8d9627b --- /dev/null +++ b/palindrome_partitioning4.py @@ -0,0 +1,34 @@ +# 1745. Palindrome Partitioning IV + +""" +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 a palindrome if it is the same string when reversed +""" + + +class Solution(object): + def checkPartitioning(self, s): + """ + :type s: str + :rtype: bool + """ + n = len(s) + dp = [[False] * n for _ in range(n)] + for i in range(n - 1, -1, -1): + for j in range(n): + if i >= j: + dp[i][j] = True + elif s[i] == s[j]: + dp[i][j] = dp[i + 1][j - 1] + for i in range(1, n): + for j in range(i + 1, n): + if dp[0][i - 1] and dp[i][j - 1] and dp[j][n - 1]: + return True + return False + + +if __name__ == "__main__": + obj = Solution() + print(obj.checkPartitioning("abcbdd")) + print(obj.checkPartitioning("bcbddxy")) |