欢迎关注本人的微信公众号AI_Engine
国庆归来,依旧精彩。leetcode系列第6篇~
题目:
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入:"babad"
输出:"bab"
注意:"aba" 也是一个有效答案。
示例 2:
输入:"cbbd"
输出:"bb"
答案:
分析:
这道题是一道经典的算法题,也是各大互联网公司面试中出现的高频面试题,在近2年内考察该面试题的公司包括:谷歌,苹果,小米,字节跳动,腾讯,阿里,百度,今日头条,华为,微软…实在是太多了,就不一一枚举了。这同时也充分体现了该题的重要程度!总而言之,必须掌握。那么现在我们就来具体的分析一下这道在leetcode的中等难度的题目,小G同学一定是用最通俗的方式对知识进行讲解,如果还有疑问可以单点沟通,同时也希望您能坚持把这篇文章读完。这道题我使用的是最流行的解法:动态规划。动态规划背后的基本思想非常简单,其实就是当要解决一个给定问题时,我们对其子问题进行求解,再根据子问题的答案归纳总结出给定问题的答案,其中这个‘归纳总结’又叫做状态转移方程(我们先不管它叫啥,暂时叫它小转)。我们来举个例子,小明(对,又是小明)要回家上楼梯且总共10个台阶,小明个子比较矮,每次在不扯着蛋的时候最多能上2个台阶,问小明上这10个台阶总共有多少种上法。这道题就是典型的动态规划入门问题,有的同学说这道题暴力求解就完全可以解答,但是要是小明是登山呢?爬长城呢?暴力破解是不是就有点过于暴力了?所以动态规划就是为了‘温柔’而诞生的。那么我们现在针对小明上楼梯的这个问题进行分析,当小明走到最后一个环节的时候,拢共分2种情况:1.剩2个台阶,2.剩1个台阶。对于第1种情况:他要么是从第8个台阶直接走到第10个台阶。要么从第8个台阶上到第9个台阶,再上到第10个台阶。对于第2种情况:就是从第9个台阶开始只走1个台阶到第10个台阶。也就是说,如果小明想走到第10个台阶,他一定是从第8个台阶或者第9个台阶起步的,如图所示:
现在我们进一步思考,如果从地面到第8个台阶有x种方法,从地面到第9个台阶有y种方法,那么从地面到第10个台阶就有x+y种方法,即f(10) = f(9) + f(8),所以对于f(n)就有f(n) = f(n-1) + f(n-2)。这就是一个递归的过程了,当n=1或者2的时候,我们就会返回一个临界值。至此,爬楼梯的动态规划建模已经完成,而且小转我们其实已经找到了,就是f(n) = f(n-1) + f(n-2),f(1)=1,f(2)=2。以上就是动态规划的入门分析,个人的思路就是降维寻找子问题,然后确定状态转移方程。现在我们回到这道leetcode题目,我们以示例1的s="babad”为例,那么他的回文子串就是bab和aba(简单理解成左右对称的子串)。我们首先用f[i][j] 表示从i 到j的子串是否是回文子串,那么当j-i<=1时就有两种情况:1.只有一个字符,比如a,必定是回文字符串。2.有两个字符的子串,如aa,ab,这种情况只要s[i]与s[j]相等时就是回文子串,否则就不是。好了,现在我们将j-i<=1的情况分析完了,我们来看看j-i>1的情况。假设f[i][j] 为回文,那么f[i+1][j-1]必定为回文,且s[i]=s[j],否则f[i][j]就不是回文。如盗图所示:
因此我们可以寻找到这样的小转(状态转移方程):
现在我们来着重看一下代码实现:首先创建记录最长回文子串和子串长度的变量long_sub_str和long_sub_len,然后依据原始字符串创建出一个方便记录的dp矩阵:dp = [[0] * length for i in range(length)],且初始化均为0,当我们发现满足状态转移方程时更新为1。现在我们通过一个外层循环从头开始遍历原始字符串,然后利用内层循环搜索回文字符串,这也是内层循环的最大长度为外层循环的当前索引值的原因。然后就是在搜索的过程中依据状态转移方程进行条件判断,更新dp矩阵,并记录出最长的回文子串。最终dp矩阵的如图所示(画的比较挫,hiahiahia):
这道题是我分析动态规划的第一道题目,如果哪里做的不够好,希望各位专家,老师,同学多多指正指导指教。夜深了,各位码神早点休息,明天还要继续奋斗,祝愿各位工作顺利,每天开心!
网友评论