每日leetcode第0067天 0131. Palindrome Partitioning

这真的是一道好题目,做得我用尽浑身解数。

虽然难度是中等,但绝不是普通的中等难度题。

虽说主体是回溯算法,但是为了优化时间,避免重复判断回文子串,需要使用动态规划来进行预处理。

 

使用一个bool二维数组is_palindrome来储存子串是否回文。i起始字母j结尾字母。

这个预处理特别有意思,先要将一个字母自己给标为1。

接下来我要判断一个子串是不是回文串找到状态转移方程式,

1.头尾两个字母得是一样的。

2.夹在中间的内容本身是一个回文子串。

于是方程式有了:

is_palindrome[i][j] = s[i] == s[j] && is_palindrome[i + 1][j – 1];

但是我发现要找的数据[i + 1][j – 1]在[i][j]的左下角,

所以遍历方式要选择从下往上,–i的方式。

而且我在excel上打表格还发现,相邻的两个字母的左下角肯定是0,但相邻两个字母一样也应该是回文子串才对。

所以我还得去判断j – i是不是1,是的话只判断这俩字母是否相等。

完整的状态转移方程式就有了:

is_palindrome[i][j] = (j – i == 1) ? (s[i] == s[j]) : (s[i] == s[j] && is_palindrome[i + 1][j – 1]);

这也太长了吧!于是我还是选择用if-else语句拉倒了。

写完后立马打印看一下和Excel手画的表格数据是否一致。好吧,一致,还算顺利。

 

热血澎湃的预处理结束后,开始了深度优先搜索。

非常中规中矩的回溯,也非常考验基本功。

写完后跑一遍,成功。

我使用的测试串是aabbaca,这个串真是啥都有,哈哈哈。



关于樊轶群

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

发表评论

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