专栏首页苦逼的码农经典面试题:最长回文子串

经典面试题:最长回文子串

回文串是面试常常遇到的问题(虽然问题本身没啥意义),本文就告诉你回文串问题的核心思想是什么。

首先,明确一下什:回文串就是正着读和反着读都一样的字符串

比如说字符串abaabba都是回文串,因为它们对称,反过来还是和本身一样。反之,字符串abac就不是回文串。

可以看到回文串的的长度可能是奇数,也可能是偶数,这就添加了回文串问题的难度,解决该类问题的核心是双指针。下面就通过一道最长回文子串的问题来具体理解一下回文串问题:

string longestPalindrome(string s) {}

一、思考

对于这个问题,我们首先应该思考的是,给一个字符串s,如何在s中找到一个回文子串?

有一个很有趣的思路:既然回文串是一个正着反着读都一样的字符串,那么如果我们把s反转,称为s',然后在ss'中寻找最长公共子串,这样应该就能找到最长回文子串。

比如说字符串abacd,反过来是dcaba,它俩的最长公共子串是aba,也就是最长回文子串。

但是这个思路是错误的,比如说字符串aacxycaa,反转之后是aacyxcaa,最长公共子串是aac,但是最长回文子串应该是aa

虽然这个思路不正确,但是这种把问题转化为其他形式的思考方式是非常值得提倡的

下面,就来说一下正确的思路,如何使用双指针。

寻找回文串的问题核心思想是:从中间开始向两边扩散来判断回文串。对于最长回文子串,就是这个意思:

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

但是呢,我们刚才也说了,回文串的长度可能是奇数也可能是偶数,如果是abba这种情况,没有一个中心字符,上面的算法就没辙了。所以我们可以修改一下:

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

PS:读者可能发现这里的索引会越界,等会会处理。

二、代码实现

按照上面的思路,先要实现一个函数来寻找最长回文串,这个函数是有点技巧的:

为什么要传入两个指针lr呢?因为这样实现可以同时处理回文串长度为奇数和偶数的情况

for 0 <= i < len(s):
    # 找到以 s[i] 为中心的回文串
    palindrome(s, i, i)
    # 找到以 s[i] 和 s[i+1] 为中心的回文串
    palindrome(s, i, i + 1)
    更新答案

下面看下longestPalindrome的完整代码:

至此,这道最长回文子串的问题就解决了,时间复杂度 O(N^2),空间复杂度 O(1)。

值得一提的是,这个问题可以用动态规划方法解决,时间复杂度一样,但是空间复杂度至少要 O(N^2) 来存储 DP table。这道题是少有的动态规划非最优解法的问题。

另外,这个问题还有一个巧妙的解法,时间复杂度只需要 O(N),不过该解法比较复杂,我个人认为没必要掌握。该算法的名字叫 Manacher's Algorithm(马拉车算法),有兴趣的读者可以自行搜索一下。

本文分享自微信公众号 - 苦逼的码农(di201805),作者:labuladong

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法面试题:超详细!如何找到字符串中的最长回文子串?

    小史:只要先对比第一个字符和倒数第一个字符,再对比第二个字符和倒数第二个字符,以此类推。如果都相等,那就是回文串了。

    帅地
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    帅地
  • 每日一题1:回文整数

    分析:有人可能会把它转化为字符串,然后在来逐一比较,显然这在处理速度上是比较慢的。下面是我推荐的两种做法:

    帅地
  • 经典面试题:最长回文子串

    回文串是面试常常遇到的问题(虽然问题本身没啥意义),本文就告诉你回文串问题的核心思想是什么。

    乔戈里
  • 算法面试题:超详细!如何找到字符串中的最长回文子串?

    小史:只要先对比第一个字符和倒数第一个字符,再对比第二个字符和倒数第二个字符,以此类推。如果都相等,那就是回文串了。

    帅地
  • 几道 BAT 算法面试中经常问的「字符串」问题

    题目来源于 LeetCode 第 125 号问题:验证回文串。这道题目是 初级程序员 在面试的时候经常遇到的一道算法题,而且面试官喜欢面试者手写!

    乔戈里
  • 几道 BAT 算法面试中经常问的「字符串」问题

    题目来源于 LeetCode 第 125 号问题:验证回文串。这道题目是 初级程序员 在面试的时候经常遇到的一道算法题,而且面试官喜欢面试者手写!

    五分钟学算法
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    五分钟学算法
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    帅地
  • 技术 | Python从零开始系列连载(二十五)

    为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

    灯塔大数据

扫码关注云+社区

领取腾讯云代金券