diff options
Diffstat (limited to 'palindrome_partitioning4.c')
-rw-r--r-- | palindrome_partitioning4.c | 45 |
1 files changed, 45 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 +} |