最长回文子串解法

问题描述 投票:0回答:2

在完成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]
python palindrome
2个回答
2
投票

给定

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 从左到右遍历字符串并且不向后走;这段代码通过字符串一次性找到答案。
  • 分支是
  • 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]

 正在询问“从这个位置向后看,最著名的回文长度和向前一个字符,是否有一个以第二个字符结尾的 2 个字符回文?”。 

elif 测试

s[j-l-1: j+1]

 会进一步回溯一个字符,只要它不回溯到字符串的开头,
j-l > 0

如果它发现它位于比已知的回文更长的回文的末尾,则会将开始

i

 和长度 
l
 更新为当前回文。

否则,

j

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


0
投票
def check_palindrome(inp): ot = [] n = len(inp) - 1 while n >= 0: ot.append(inp[n]) n = n - 1 ot_stg = ''.join(ot) if inp == ot_stg: return True else: return False def palindrome_substring(inp): n = len(inp) pal_str = "" for i in range(0, n): for j in range(i+1, n): if inp[i] == inp[j]: sub_str = inp[i:j+1] if check_palindrome(sub_str) and len(pal_str) < len(sub_str): pal_str = sub_str return pal_str
    
© www.soinside.com 2019 - 2024. All rights reserved.