Readme

1745.Palindrome-Partitioning-IV

关于判定一个字符串中的substring是否为回文串，区间型的DP是最常规的手段。在这里，我们可以提前用o(N^2)的时间预处理s，得到dp[i][j]表示任意一个子区间是否为回文串。

然后我们再循环遍历两个分界点i和j，将s分割为三部分，这样只需要直接调用dp[0][i],dp[i+1][j-1],dp[j+1][n-1]就可以知道这三部分是否分别都是回文串。这两层循环的时间复杂度也是o(N^2).

另外，本题有线性时间复杂度的Manacher算法。