问题描述

给定一个字符串，编写一个函数来查找字符串中的最长回文子串。 比如给定字符串 babad，最长的回文子串是 bab 或者 aba。 或者给定字符串 cbbd，最长的回文子串是 bb。

测试代码

assert.Equal(t, "bab", LongestPalindrome("babad"))
assert.Equal(t, "bb", LongestPalindrome("cbbd"))
assert.Equal(t, "a", LongestPalindrome("a"))

解决思路

实现这个问题的一个简单方法是枚举所有的子串，然后判断子串是否是回文子串，然后找到最长的回文子串。 但是这个方法太暴力，时间复杂度是O(n^3)，效率比较低。

实现一个基于中心扩展法的算法，可以将时间复杂度降低到O(n^2)。

回文有分别由奇数和偶数两种情况，所以我们可以分别以每个字符为中心，或者以两个字符的中间为中心，向两边扩展，找到以这个字符为中心的最长回文子串。

1. 遍历字符串，以每个字符为中心，向两边扩展，找到以这个字符为中心的最长回文子串。
2. 遍历字符串，以每两个字符的中间为中心，向两边扩展，找到以这两个字符为中心的最长回文子串。
3. 比较两种情况，找到最长的回文子串。

代码解析

算法的工作原理如下：

• 行 2-4: 如果输入字符串text的长度小于2，直接返回该字符串，因为长度为0或1的字符串本身就是回文。
• 行 7: 初始化start和maxLength变量，分别用于记录当前找到的最长回文子串的起始位置和长度。初始时，假设最长回文子串的长度为1（单个字符）。
• 行 8-26: 使用外层循环遍历字符串，idx变量表示当前考虑的子串的起始位置。
  • 行 9: 如果当前位置到字符串末尾的长度小于已找到的最长回文子串的一半，则不可能找到更长的回文子串，循环结束。
  • 行 12-15: 内层循环1，用于处理连续相同字符的情况。begin和end初始化为当前索引idx，如果end后一个字符与当前相同，则end后移。
  • 行 16: 更新idx为end + 1，准备下一次迭代。
  • 行 17-20: 内层循环2，用于扩展当前考虑的子串。如果end后一个字符与begin前一个字符相同，则扩展begin和end的范围，即向两边扩展。
  • 行 21-24: 计算扩展后的子串长度，并判断是否为当前找到的最长回文子串。如果是，则更新start和maxLength。 -行 27: 使用start和maxLength截取并返回最长回文子串。

总结

所有的后端面试常见的问题，我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群，一起学习和进步。

欢迎大家关注 入职啦 (公众号: ruzhila) ，获取更多有趣的编程挑战题和技术干货！