开始觉得挺简单的 写完发现这个时间超限了：
class Solution:
def longestPalindrome(self, s: str) -> str:
# longest palindromic substring lenth < 1000
#NULL
string = s
if len(string) == 0:
return ''
# ---
# regular
# a not empty string must have 1 letterd palindromic substring:string[0]
longestPalindSubStringLength = 1
longestPalindSubString = string[0]
for start in range(len(string)):
for end in range(start + 1, len(string) +1): #[] operator is right open interval,will not count "end" if no +1
# one letter
if len(string[start:end]) == 1:
continue
if (self.isPalind(string[start:end])):
if len(string[start:end]) > longestPalindSubStringLength:# > will get bab ;>= will get aba. I prefer simple one
longestPalindSubStringLength = len(string[start:end])
longestPalindSubString = string[start:end]
return longestPalindSubString def isPalind(self, substring: str) -> bool:
#notice substring >= 2
substringlength = len(substring) looplimit = substringlength // 2
for index in range(0, looplimit):
if substring[index] != substring[substringlength-1 -index]: # axisymmetric
return False
else:
pass
# run to here without return mean palindromic
return True
"abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa"
用pycharm跑了下 要4秒，结果就是它自己。[testcase:85]
发现之前判断轴对称的方法太低级了 不用逐位判断 轴对称的前一半和后一半的逆序是同一字符串即可。
class Solution:
def longestPalindrome(self, s: str) -> str:
# longest palindromic substring lenth < 1000
#NULL
string = s
if len(string) == 0:
return ''
# ---
# regular
# a not empty string must have 1 letterd palindromic substring:string[0]
longestPalindSubStringLength = 1
longestPalindSubString = string[0]
for start in range(len(string)):
for end in range(start + 1, len(string) +1): #[] operator is right open interval,will not count "end" if no +1
# one letter
if len(string[start:end]) == 1:
continue
if (self.isPalind(string[start:end])):
if len(string[start:end]) > longestPalindSubStringLength: #> mean bab;>= mean aba
longestPalindSubStringLength = len(string[start:end])
longestPalindSubString = string[start:end]
return longestPalindSubString def isPalind(self, substring: str) -> bool:
#notice substring >= 2
substringlength = len(substring) if(substringlength %2) == 1:
#odd
temp1 = substring[0:substringlength // 2 +1]
temp2 = substring[substringlength:substringlength // 2 - 1:-1]
if temp1 == temp2:
return True
else:
return False
else:
#even
temp1 = substring[0:substringlength//2]
temp2 = substring[substringlength:substringlength//2 -1:-1]
if temp1 == temp2:
return True
else:
return False
testcase:95
"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"
f比g多一个
testcase:98
def longestPalindrome(self, s: str) -> str:
# longest palindromic substring lenth < 1000
# NULL
if len(s) == 0:
return ''
# ---
# regular
# a not empty string must have 1 letterd palindromic substring:string[0]
longestPalindSubStringLength = 1
longestPalindSubString = s[0]
for start in range(len(s)):
for end in range(start + 1, len(s) + 1): # [] operator is right open interval,will not count "end" if no +1
# left to right for end in range(start + 1, len(s) + 1)
#from right to left range(length -1,-)
# one letter
if len(s[start:end]) == 1 or len(s[start:end]) <= longestPalindSubStringLength:
continue
if (self.isPalind(s[start:end])):
if len(s[start:end]) > longestPalindSubStringLength:
longestPalindSubStringLength = len(s[start:end])
longestPalindSubString = s[start:end]
return longestPalindSubString def isPalind(self, substring: str) -> bool:
# notice substring >= 2
substringlength = len(substring) if (substringlength % 2) == 1:
# odd
temp1 = substring[0:substringlength // 2 + 1]
temp2 = substring[substringlength:substringlength // 2 - 1:-1]
if temp1 == temp2:
return True
else:
return False
else:
# even
temp1 = substring[0:substringlength // 2]
temp2 = substring[substringlength:substringlength // 2 - 1:-1]
if temp1 == temp2:
return True
else:
return False
单个testcase耗时从500ms降到了200ms 但是总是到100/108的时候报TLE，换方法，下篇再说。