思路分析
回文串问题算是非常典型常见的题目了。这道题要找最长回文子串 其实有一个非常经典高效的算法 马拉车算法 时间复杂度和空间复杂度都为O(n) 不过马拉车算法就是太巧妙了 巧妙到只适合这一个问题 可扩展或者可借鉴的地方不是很多 往往这种奇技淫巧记住了也容易忘 有兴趣的可以去搜一下了解了解 还有一种方法就是动态规划 但比较搞笑的是 用动态规划解决这一问题 是简洁和复杂度低两样都不占 其时空复杂度都是O(n的平方) 如果用动态规划 更像是强行“炫技“了。后面会有很多动态规划的题目 到时候再去体会动态规划的魅力吧。
我自己总结这些算法题 从来都不是追求最优解 而是追求最优和容易记忆之间的平衡 毕竟面试遇到的时候 可以第一时间想到一个较为合适的解才是最重要的。
这道题最“不错“的解法是中心扩散法。不要被它这个名字吓到了 其实很简单 我描述一遍 遍历给定的字符串 从前向后遍历字符 以它以及它和它的下一个为中心尝试向两边扩散 看看是不是满足是回文串 如果是就继续扩散 直到不满足 记录下最大长度。这里之所以要分别以 它 以及 它和它的下一个 为中心 是因为回文串有的是“aba” 有的是“abba” 即中心可能包含一个或两个字符 所以要都要进行讨论。
这样一来 最外面遍历一次 每个字符也要向两边扩散遍历 总复杂度为O(n的平方)。
代码:
class Solution(object): def longestPalindrome(self, s): :type s: str :rtype: str def is_hui(s,i,j):#传入字符串s 和当前左右边界i和j 返回以i j位置为中心的最长回文子串 lenth len(s) #如果满足回文条件且为超过边界 就一直扩散 while(i 0 and j lenth-1 and s[i] s[j]): i- 1 #扩散方式就是i减小 j增大 return [i 1,j,j-i-1]#注意边界要单独处理一下 以列表的形式返回 分别是左边界、右边界和长度 res 0 #res保存最终结果 res_i 0 res_j 0 for i in range(len(s)): a is_hui(s,i,i) #以i位置单个字符为中心 if a[-1] res:#如果此时的长度超过历史记录 则更新 res a[-1] res_i a[0] res_j a[1] a is_hui(s,i,i 1)#以i和i的下一个双字符为中心 if a[-1] res:#如果此时的长度超过历史记录 则更新 res a[-1] res_i a[0] res_j a[1] #res_i,res_j就是最终结果的左右边界了 return s[res_i:res_j]
总之 解这个题方法很多 但我推荐中心扩散法这种简单理解并记忆的方法 尤其是方便记忆 这个优点很重要。
