文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / palindrome-partitioning-ii
文件大小:
709.00 B
下载地址:
文本预览:
## [Longest Palindromic Substring](../longest-palindromic-substring) + [Word Break](../word-break)
After running [Longest Palindromic Substring](../longest-palindromic-substring),
we got a table `P[len][index]`, that is, we can tell if `s[i..j]` is palindromic
## Apply [Word Break](../word-break)
`M[i]` means the mincut of `s[0..i]`.
When a new char comes, we have 3 choices:
* `M[i + 1] = 0`: if `s[0..i + 1]` is palindromic
* `M[i + 1] = M[i] + 1`: cut at `i`, between the old string `s[0..i]` and the new char.
* `M[i + 1] = M[j] + 1`: cut at `j`, `j from 0 -> i`, such that `s[j..i+1]` is palindromic, between the `s[0..j]` and `s[j..i + 1]`.
Our job is to find the minimum value among them.
After running [Longest Palindromic Substring](../longest-palindromic-substring),
we got a table `P[len][index]`, that is, we can tell if `s[i..j]` is palindromic
## Apply [Word Break](../word-break)
`M[i]` means the mincut of `s[0..i]`.
When a new char comes, we have 3 choices:
* `M[i + 1] = 0`: if `s[0..i + 1]` is palindromic
* `M[i + 1] = M[i] + 1`: cut at `i`, between the old string `s[0..i]` and the new char.
* `M[i + 1] = M[j] + 1`: cut at `j`, `j from 0 -> i`, such that `s[j..i+1]` is palindromic, between the `s[0..j]` and `s[j..i + 1]`.
Our job is to find the minimum value among them.
点赞
回复
X