aboutsummaryrefslogtreecommitdiff
path: root/palindrome_partitioning4.py
diff options
context:
space:
mode:
Diffstat (limited to 'palindrome_partitioning4.py')
-rw-r--r--palindrome_partitioning4.py34
1 files changed, 34 insertions, 0 deletions
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"))