132. 分割回文串 II

【题目】

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例:

输入: "aab"输出: 1解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

【举例】

　　str = “ABA”，str本身就是回文串，返回0. 　　str = “A|CDCDC|DAD”，最少需要切两次变成3个回文子串，所以 返回2.

【基本思路】

本题是一个经典的动态规划的题目。

定义动态规划数组dp，

dp[i]的含义是子串str[0…i]至少需要切割几次，才能把str[0…i]全部切成回文子串。那么dp[len-1]就是最后的结果。

Calculate and maintain 2 DP states:

1. pal[i][j] , which is whether s[i..j] forms a pal
2. d[i], which is the minCut for s[i..n-1]

this can be solved by two points:

1. cut[i] is the minimum of cut[j - 1] + 1 (j <= i), if [j, i] is palindrome.
2. If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and c[j] == c[i].

The 2nd point reminds us of using dp (caching).

a   b   a   |   c  c                j  i
       j-1  |  [j, i] is palindrome
   cut(j-1) +  1

思考题目：

680. 验证回文字符串 Ⅱ

题目描述 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"输出: True

示例 2:

输入: "abca"输出: True解释: 你可以删除c字符。

提示：

算法描述：

1 遍历数组 ，如果2边相等 继续遍历

2 不然需要判断

Keep checking if they are same

1. If they are Same - then just check inside and keep going till you reach the center(left==right) （前提条件）
2. If they are NOT same : You now have 2 options 2.1) Remove Left Element and Check for the Rest of String OR 2.2) Remove Right Element and Check for the Rest of the string. If either of them dont give palindrome then its not a palindorme