leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

palindrome_partitioning4.py (995B)

 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"))