最长回文子串解

Question

做完leetcode上的题后，我在复习别人的解法，发现这个运行时间快得离谱，但我没有完全理解解法。希望有人能逐行解释，尤其是 elif 语句。

据我了解，第一个 if 语句只是检查您是否反转子字符串并且它与反转后的原始子字符串匹配，但是我迷失了 elif。

class Solution:
    def longestPalindrome(self, s: str) -> str:

        if len(s) <= 1:
            return s

        i, l = 0, 0
        for j in range(len(s)):
            if s[j-l: j+1] == s[j-l: j+1][::-1]:
                i, l = j-l, l+1
                # print(s[i: i+l]) 

            elif j-l > 0 and s[j-l-1: j+1] == s[j-l-1: j+1][::-1]:
                i, l = j-l-1, l+2
                # print(s[i: i+l])

        return s[i: i+l]

Answer 1

给定 abcNOONdeRACECAR，其中 | 是遍历字符串的循环，查找返回以查看是否找到更长的回文，并且 [] 是围绕最知名的回文数，而数字是目前最知名的回文数的长度，它是这样做的：

a|bcNOONdeRACECAR [a]bcNOONdeRACECAR 1
ab|cNOONdeRACECAR [a]bcNOONdeRACECAR 1
abc|NOONdeRACECAR [a]bcNOONdeRACECAR 1
abcN|OONdeRACECAR [a]bcNOONdeRACECAR 1
abcNO|ONdeRACECAR [a]bcNOONdeRACECAR 1
abcNOO|NdeRACECAR abcN[OO]NdeRACECAR 2
abcNOON|deRACECAR abc[NOON]deRACECAR 4
abcNOONd|eRACECAR abc[NOON]deRACECAR 4
abcNOONde|RACECAR abc[NOON]deRACECAR 4
abcNOONdeR|ACECAR abc[NOON]deRACECAR 4
abcNOONdeRA|CECAR abc[NOON]deRACECAR 4
abcNOONdeRAC|ECAR abc[NOON]deRACECAR 4
abcNOONdeRACE|CAR abc[NOON]deRACECAR 4
abcNOONdeRACEC|AR abc[NOON]deRACECAR 4
abcNOONdeRACECA|R abcNOONdeR[ACECA]R 5
abcNOONdeRACECAR| abcNOONde[RACECAR] 7
RACECAR

（我觉得最大的收获是靠自己的努力）

我注意到的事情：

它以 return s[i: i+l] 结尾，所以 i 必须成为回文子串的开始，而 l 必须成为它的长度。
for j in range(len(s)) j 从左到右遍历字符串，不向后；此代码在字符串 one-pass 中找到答案。
分支是 if/elif，这意味着缺少 else，这就是“我现在还没有找到回文，什么都不做”的地方。
有注释掉显示当前最佳候选回文子串的打印语句，这有助于说明它是如何工作的，添加 else 并在其中打印可能会有所帮助。
回文可以是偶数长度 "gg"、"toot" 或奇数长度 "a"、"lol"、"racecar"。您可以将回文的长度增加 +1 或 +2。 if和elif就是这两种情况，右边加1看是不是长回文，左边加1右边加1看是不是长回文。
代码中的测试做了很多j-l，我们看到的是字符串中的当前位置减去最知名回文的长度。即索引 j 被认为是 * 在可能回文的末尾，向后看。

从头开始 s[j-l: j+1] 是 0-0 到 0+1 这是第一个字符。一个字符是回文，因此开始和长度已更新i, l = j-l, l+1这是现在最知名的候选字符。

j 移动到索引 1。现在测试 s[j-l: j+1] 正在询问“从这个位置向后看，最著名的回文长度和 one-char 向前，是否有 2 个字符的回文在第二个字符处结束？”。

elif 测试 s[j-l-1: j+1] 进一步回溯一个字符，只要它不回溯到字符串的开头，j-l > 0.

如果它发现它位于比最知名的回文更长的回文的末尾，它会将开始 i 和长度 l 更新为当前回文。

否则，j 将一个字符移动到字符串中。随着 j 进一步移动，回文只能增加 1 或 2 的长度，不能一次增加 5。因此，要么回文增长+1 回文或+2，要么我们已经越过回文并进入未知领域。在未知领域，我们只寻找比最知名的回文更长的回文，而不是再次从 1 开始。

最长回文子串解

longest palindromic substring solution

python

palindrome