Amazon面试题:寻找最长回文子串

本文由码农网 – 小峰原创翻译,转载请看清文末的转载要求,欢迎参与我们的付费投稿计划

这个问题是Amazon在面试中提出来的。

给定一个字符串,找到最长的回文连续子字符串。如果不止一个,则返回一个即可。

例如,“aabcdcb”的最长回文子串是“bcdcb”。 “bananas”的最长回文子串是“anana”。

解决方案

我们可以用蛮力计算出 O(N^3)中最长的回文连续子串。遍历数组的每个子串并检查它是否是回文的。

def is_palindrome(s):
    return s[::-1] == s

def longest_palindrome(s):
    longest = ''
    for i in range(len(s) - 1):
        for j in range(1, len(s)):
            substring = s[i:j]
            if is_palindrome(substring) and len(substring) > len(longest):
                longest = substring
    return longest

当然,我们也可以通过使用动态编程来存储重复的计算,从而减少运行此算法所需的时间。让我们制定一个N乘N的表格A,其中N是输入字符串的长度。然后,在每个索引A[i][j]中存放从s[i:j]构成的子串是否是回文。我们将使用到以下关系:

  • 所有长度为1的字符串都是回文
  • 如果s[1:-1]是回文且s的第一个和最后一个字符相同,则s为回文

所以,当我们填充表格时,我们可以做到以下几点:

  • 首先,将每个项目沿着对角线’A [i:i]设置为true,因为长度为1的字符串总是回文
  • 然后,检查A[i:i+1],如果A[i] == A[i + 1]则将其设置为true,否则返回false(检查所有长度为2的字符串)
  • 最后,从上到下,从左到右迭代矩阵,只检查对角线上部。请注意,ji小是没有意义的,这就是为什么我们只需要处理一半矩阵的原因。仅当A[i + 1][j - 1]为真并且A[i] == A[j]时,才将A[i][j]设置为真。
  • 跟踪我们迄今为止发现的最长的回文子字符串。

我们来看一个“bananas”的例子:

b a n a n a s
b t f f f f f f
a t f t f t f
n t f t f f
a t f f f
n t f f
a t f
s t

def longest_palindrome(s):从表格中可以看到,这里最长的回文子串是“anana”,因为A[1:5]是表中显示为true的最长子串。

    if not s:
        return ''

    longest = s[0]
    A = [[None for _ in range(len(s))] for _ in range(len(s))]

    # Set all substrings of length 1 to be true
    for i in range(len(s)):
        A[i][i] = True

    # Try all substrings of length 2
    for i in range(len(s) - 1):
        A[i][i + 1] = s[i] == s[i + 1]

    i, k = 0, 3
    while k <= len(s):
        while i < (len(s) - k + 1) :
            j = i + k - 1
            A[i][j] = A[i + 1][j - 1] and s[i] == s[j]
            # Update longest if necessary
            if A[i][j] and len(s[i:j + 1]) > len(longest):
                longest = s[i:j + 1]
            i += 1
        k += 1
        i = 0
    return longest

这个时间复杂度和空间复杂度为O(N^2)。

如果你正在准备技术面试,那么请务必多收集像这样来自顶尖科技公司的最新面试问题。

祝面试好运!

译文链接:http://www.codeceo.com/article/amazon-find-longest-palindromic-substring.html
英文原文:Finding the longest palindromic substring
翻译作者:码农网 – 小峰
转载必须在正文中标注并保留原文链接、译文链接和译者等信息。]