lambda和key的回文题使用

Question

大家好，我在 algoExpert 平台上解决这个问题，但我很难理解 longest 和 currentLongest 到底在做什么。

def longestPalindromicSubstring(string):
  currentLongest = [0, 1]
  for i in range(1, len(string)):
    odd = getLongestPalindromeFrom(string, i - 1, i + 1)
    even = getLongestPalidromeFrom(string, i - 1, i)
    longest = max(odd, even, key=lambda x: x[1] - x[0])
    currentLongest = max(longest, currentLongest, key=lambda x: x[1] - x[0])
  return string[currentLongest[0] : currentLongest[1]]

def getLongestPalindromeFrom(string, leftIdx, rightIdx):
  while leftIdx >= 0 and rightIdx < len(string):
    if string[leftIdx] != string[rightIdx]:
      break
    leftIdx -= 1
    rightIdx += 1
  return [leftIdx + 1, rightIdx]

刚开始，我不太清楚currentLongest = [0, 1]是干什么的，是不是说它会有2个值？奇数和偶数 return 是索引数组吗？ longest 我知道它取奇数和偶数之间的最大值，key 似乎取了**匿名函数 lambda ** 但我不太确定 key 做了什么以及 x: x[1] - x[0] 的作用。我也不明白 currentLongest 用最大值做什么。比如传递 longest 和 currentLongest 的目的是什么？它们都是列表，所以我不完全确定那里发生了什么。在 return 中，如果我们在 longest 上得到类似 [3:9] 的内容，我认为我们所做的只是将字符串切片为 string(3:9)，但列表的使用让我感到困惑max 和 key:lambda 让我更加困惑。感谢您的帮助！

说明：编写一个函数，给定一个字符串，return 是它最长的回文子串。回文被定义为向前和向后书写相同的字符串。请注意，单字符字符串是回文。你可以假设只有一个最长的回文子串。

示例输入：

string = "abaxyzzyxf"

示例输出：

"xyzzyx"

感谢 Daniel Hao 要求更多说明，感谢 Prasad Darshana 就如何更好地格式化我的代码行提出建议。我是 Stack Overflow 的新手，这对我很有帮助，所以我可以知道如何格式化并在下次提出更好的问题！

Answer 1

currentLongest = [0, 1]，这是最初的假设。在这段代码中，假设最长的回文子串是一个从 0 开始到 1 结束的字符串。

例如：

如果给定的字符串是 abcdc，它假定 currentLongest 为 a（从索引 0 到 1）。

然后在 longestPalindromicSubstring 函数的 for 循环中，它检查索引并将其增加 1。在 even 和 odd 的情况下。它得到偶数长度和奇数长度的子串来检查。您可以通过传递给 getLongestPalidromeFrom 函数的值来检查长度。 ( (i-1),(i),(i+1) length= 3 odd ).

在 getLongestPalidromeFrom 函数中，它将长度增加两倍并检查它是否回文。然后 return 可以生成的最长回文子串 从给定点开始 .

in longest 它检查 odd 和 even 长度字符串中最长的子字符串是什么。然后在 currentLongest 中，它将新的最长值与先前的最长 (curentLongest) 值进行比较。

记住currentLongest, longest中的索引是子串的起点和终点的索引。所以长度等于x[1]-x[0]。 lambda 函数。

我的解释中可能存在一些索引错误。但完全是这样。

Answer 2

currentLongest 和 longest 之间的差异

currentLongest 跟踪迄今为止通过迭代找到的最长回文的开始和结束索引。 currentLongest 被初始化为 currentLongest = [0,1]，因此即使字符串长度为 1 个字符，for 循环也不会执行并且 return 单个字符（通过 return string[currentLongest[0]:currentLongest[1]]）。

longest 保留在单次迭代中找到的最长回文的开始和结束索引。这是通过对 2 个数组执行 lambda 运算来检索的：奇数和偶数。

x: x[1] - x[0] 的作用是什么？

lambda运算以这种方式比较两个数组，奇数和偶数（x表示每个数组）：它取每个数组并从结束索引（1）中减去起始索引（0），并输出数组具有开始和结束索引之间的最大差异/距离。 (表示最长子串回文)

Answer 3

经过一番猜测，我想我明白了，建议您尝试以下代码，看看是否可以帮助您更好地理解 posted 代码： [注释]这不是直接的答案，而是试图揭开复杂代码的神秘面纱并提出解决此问题的替代方案，或作为参考。

def longestPalindromeSub(string):
    N = len(string)
    for i in range(N)[::-1]:
        for idx in range(N-i):
            word = string[idx: idx+i+1]
            if word == word[::-1]:     # palindrome is symmetric 
               return word
    return ''  # not found

运行字='racecar'

>>> print(longestPalindromeSub(word))
    `racecar`

>>> print(longestPalindromeSub('mississippi'))
    'ississi'

lambda和key的回文题使用

Palindrome question use of lambda and key

python

algorithm

data-structures