0°

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

内容预览:
  • 点击上方 &;程序员小乐&; ,选择“置顶公众号”,第一时间送达! 每日英文...~
  • 例如,“aabcdcb”的最长回文子串是“bcdcb”~
  • 推荐阅读 看完本文有收获?请转发分享给更多人关注「程序员小乐」,提升...~

始发于微信公众号: 程序员小乐

专注于编程、互联网动态。最终将总结的技术、心得、经验(数据结构与算法、源码分析等)分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经点击上方 “程序员小乐” ,选择“置顶公众号”,第一时间送达!


每日英文
No matter what happens, don’t give up, insist, will have unexpected scenery.
不管发生什么,都不要放弃,坚持走下去,肯定会有意想不到的风景。

乐乐有话说
当自律便成为一种习惯,一种生活方式,你的人格和智慧就会变得更加完美。 

这个问题是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的字符串)

  • 最后,从上到下,从左到右迭代矩阵,只检查对角线上部。请注意,j比i小是没有意义的,这就是为什么我们只需要处理一半矩阵的原因。仅当A[i + 1][j – 1]为真并且A[i] == A[j]时,才将A[i][j]设置为真。

  • 跟踪我们迄今为止发现的最长的回文子字符串。

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

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

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

原文:

https://interviewcache.com/blog/longest-palindromic-substring/

著作权归作者所有,欢迎投稿。

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


推荐阅读






看完本文有收获?请转发分享给更多人
关注「程序员小乐」,提升技能

以上就是:Amazon算法面试题:寻找最长回文子串 的全部内容。

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢。
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论