在完成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]
给定
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 开始。
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