[LeetCode]Palindrome Partitioning II

DP[i]表示s中前i个char的最小cut数。我们可以得到递推方程：

• DP[i] = min(DP[j ] + 1), 如果存在j并且j满足条件s[j, i]为palindrome
• 否则DP[i] = i - 1

我们有两种方法可以实现。因为找string的所有回文一般有两种方法。第一种，我们用另外一个二维数组isPalin[i][j]来表示s[i, j]是否为回文。我们可以在更新DP的时候同时更新isPalin，空间复杂度O(n^2)，时间复杂度O(n)，代码如下：

第二种，我们可以根据从每个字符开始向两边展开来求所有的回文，检测到回文的时候就更新对应DP的位置。因为我们看到当前substring不是回文就会立刻中断，虽然时间复杂度worst case也是O(n^2)，但整体来讲会稍微快一点，并且不需要额外空间。但因为DP需要空间，所以整体空间复杂度是O(n)，代码如下：