aboutsummaryrefslogtreecommitdiff
path: root/palindrome_partitioning4.py
blob: 8d9627bde6eef89856b83cd31c049ac133376fe5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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"))