【题目】
给定一个字符串 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:
this can be solved by two points:
cut[i]
is the minimum of cut[j - 1] + 1 (j <= i)
, if [j, i]
is palindrome.[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
思考题目:
s
,最多删除一个字符。判断是否能成为回文字符串。示例 1:
输入: "aba"输出: True
示例 2:
输入: "abca"输出: True解释: 你可以删除c字符。
提示:
算法描述:
1 遍历数组 ,如果2边相等 继续遍历
2 不然需要判断
Keep checking if they are same
(left==right) (前提条件)
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