aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-07-08 21:22:27 -0600
committerJack Sangdahl <[email protected]>2024-07-08 21:22:27 -0600
commit3da2313c973529e042dbaf522166e10c3f3a94ae (patch)
treeeafa027a092d7050778f2737766ef35b041f16d2
parentd4a293cacfd8085e968e4341b9b779a294ff938b (diff)
downloadleetcode-3da2313c973529e042dbaf522166e10c3f3a94ae.tar.gz
leetcode-3da2313c973529e042dbaf522166e10c3f3a94ae.zip
1745. palindrome partitioning iv
-rw-r--r--palindrome_partitioning4.c45
-rw-r--r--palindrome_partitioning4.py34
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"))