aboutsummaryrefslogtreecommitdiff
path: root/palindrome_partitioning4.c
diff options
context:
space:
mode:
Diffstat (limited to 'palindrome_partitioning4.c')
-rw-r--r--palindrome_partitioning4.c45
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
+}