leetcode 1745

给你一个字符串s，如果可以将它分割成三个非空回文子字符串，那么返回true，否则返回false。

思路： 由于需要分割为三个非空子字符串，那么可以从第一个字符和最后一个字符下手，我们可以记录下来，以第一个字符开头的回文字符串，以最后一个字符结尾的回文字符串，然后再判断中间的字符串是否是回文字符串，由于分割非空的要求，需要保证中间的字符串存在。 
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
def checkPartitioning(self, s: str) -> bool:
    n = len(s)
    # dp[i][j] 表示 s[i...j] 的字符串是否是回文字符串
    dp = [[True for _ in range(n)] for _ in range(n)]

    for i in range(n-1,-1,-1):
        for j in range(i+1, n):
            dp[i][j] = (s[i] == s[j]) & dp[i+1][j-1]

    # start[] 表示以第一个字符开头，数组的值为回文字符串结尾的下标
    start = []
    # end[] 表示以最后一个字符结尾，数组的值为回文字符串开头的下标
    end = []
    for i in range(1,n-1):
        t = s[:i]
        if t == t[::-1]:
            start.append(i-1)

    for i in range(n-1,1,-1):
        t = s[i:]
        if t == t[::-1]:
            end.append(i)

    # 注意 start 和 end都为有序，start从小到大，end从大到小
    for part1 in start:
        for part2 in end:
            # 如果中间没有字符串了，则直接跳出循环
            if part1 + 1 >= part2:
                break
            # 查看中间的字符串是否回文，如果回文，则说明可以分割为3个非空回文子字符串
            if dp[part1+1][part2-1]:
                return True

    return False