每日leetcode第0068天 0132. Palindrome Partitioning II

这是昨天题目的续集。

如果我们使用深度优先算法来处理,然后在得到每一次结束的时候比较大小,似乎也可以做,但是时间复杂度较高。

所以这里选择使用两次动态规划来解决这个问题。

第一次动态规划和昨天的一样,都是做一个预处理,判断从i到j这一段是不是回文。

接下来就是这道题目的核心了,怎么来判断最小的切割次数。

我们会开设一个min_cut的数组,记录从0到right所需要的最少切割次数。

开始的时候都设置为len-1,这里为什么不需要设置成什么INT_MAX呢?

因为字符串每个字符都切割也就只需要len-1次就可以啦。

如果0-right自身就是回文串,那么就不需要切割,min_cut[right] = 0。

否则,我们要出动left了,left要一直跑到right前面停下。如果left+1到right是一个回文串的话,那么就可以判断是否这样切割更划算,也就是说min_cut[right]就从min_cut[right]和min_cut[left] + 1来取较小值。

最后输出min_cut[len – 1]即可。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。