Disclaimer: Not a Code Reviewer
Here are some short comments though:
- You're looping though twice.
- That'd make it brute force.
- Brute force does usually fail for some medium and hard questions on LeetCode.
Alternative Solution
- Here we'd loop through once:
class Solution:
def longestPalindrome(self, s):
if len(s) < 1:
return s
def isPalindrome(left, right):
return s[left:right] == s[left:right][::-1]
left, right = 0, 1
for index in range(1, len(s)):
if index - right > 0 and isPalindrome(index - right - 1, index + 1):
left, right = index - right - 1, right + 2
if index - right >= 0 and isPalindrome(index - right, index + 1):
left, right = index - right, right + 1
return s[left: left + right]
Your Solution
- I just tested your solution (marginally passes):
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 1:
return s
P = [[False] * len(s) for i in range(len(s))]
for i in range(len(s)):
P[i][i] = True
for i in range(len(s) - 1):
P[i][i + 1] = (s[i] == s[i + 1])
for s_len in range(3, len(s) + 1):
for i in range(len(s) + 1 - s_len):
P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])
ip = 0
jp = 0
max_len = 1
for i in range(len(s)):
for j in range(len(s)):
if P[i][j] and j + 1 - i > max_len:
max_len = j + 1 - i
ip = i
jp = j
continue
return s[ip:jp + 1]
Since the runtimes is high, it's possible that it would fail sometimes.
I guess LeetCode has a time limit for each problem, maybe 10 seconds would be the limit for this specific problem.
Probably based on the geolocation/time, the runtime would be different also.
Just a bit more optimization:
- Please see this line
for j in range(i + 1, len(s))::
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 1:
return s
P = [[False] * len(s) for _ in range(len(s))]
for i in range(len(s)):
P[i][i] = True
for i in range(len(s) - 1):
P[i][i + 1] = (s[i] == s[i + 1])
for s_len in range(3, len(s) + 1):
for i in range(len(s) + 1 - s_len):
P[i][i + s_len - 1] = P[i + 1][i + s_len - 2] and (s[i] == s[i + s_len - 1])
ip = 0
jp = 0
max_len = 1
for i in range(len(s)):
for j in range(i + 1, len(s)):
if P[i][j] and j + 1 - i > max_len:
max_len = j + 1 - i
ip = i
jp = j
continue
return s[ip:jp + 1]
It reduces about 1 second but still not good.
I'm sure there are more ways to optimize.
Wait a bit! There are good Python reviewers here. Would likely help you out.
With some comments:
class Solution:
def longestPalindrome(self, s):
if len(s) < 1:
return s
def isPalindrome(left, right):
return s[left:right] == s[left:right][::-1]
# We set the left pointer on the first index
# We set the right pointer on the second index
# That's the minimum true palindrome
left, right = 0, 1
# We visit the alphabets from the second index forward once
for index in range(1, len(s)):
# Here we move the right pointer twice and once checking for palindromeness
# We boundary check using index - right, to remain positive
if index - right > 0 and isPalindrome(index - right - 1, index + 1):
print(f"Step {index - 1}: Left pointer is at {index - right - 1} and Right pointer is at {index + 1}")
print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
print(f"Window length: {right}")
print(f"Before: Left is {left} and Right is {left + right}")
left, right = index - right - 1, right + 2
print(f"After: Left is {left} and Right is {left + right}")
print(f"String: {s[left: left + right]}")
print('#' * 50)
if index - right >= 0 and isPalindrome(index - right, index + 1):
print(f"Step {index - 1}: Left pointer is at {index - right} and Right pointer is at {index + 1}")
print(f"Palindromeness start: {index - right - 1} - Palindromeness end: {index + 1}")
print(f"Window length: {right + 1}")
print(f"Before: Left is {left} and Right is {left + right}")
left, right = index - right, right + 1
print(f"After: Left is {left} and Right is {left + right}")
print(f"String: {s[left: left + right]}")
print('#' * 50)
return s[left: left + right]
Solution().longestPalindrome("glwhcebdjbdroiurzfxxrbhzibilmcfasshhtyngwrsnbdpzgjphujzuawbebyhvxfhtoozcitaqibvvowyluvdbvoqikgojxcefzpdgahujuxpiclrrmalncdrotsgkpnfyujgvmhydrzdpiudkfchtklsaprptkzhwxsgafsvkahkbsighlyhjvbburdfjdfvjbaiivqxdqwivsjzztzkzygcsyxlvvwlckbsmvwjvrhvqfewjxgefeowfhrcturolvfgxilqdqvitbcebuooclugypurlsbdfquzsqngbscqwlrdpxeahricvtfqpnrfwbyjvahrtosovsbzhxtutyfjwjbpkfujeoueykmbcjtluuxvmffwgqjgrtsxtdimsescgahnudmsmyfijtfrcbkibbypenxnpiozzrnljazjgrftitldcueswqitrcvjzvlhionutppppzxoepvtzhkzjetpfqsuirdcyqfjsqhdewswldawhdyijhpqtrwgyfmmyhhkrafisicstqxokdmynnnqxaekzcgygsuzfiguujyxowqdfylesbzhnpznayzlinerzdqjrylyfzndgqokovabhzuskwozuxcsmyclvfwkbimhkdmjacesnvorrrvdwcgfewchbsyzrkktsjxgyybgwbvktvxyurufsrdufcunnfswqddukqrxyrueienhccpeuqbkbumlpxnudmwqdkzvsqsozkifpznwapxaxdclxjxuciyulsbxvwdoiolgxkhlrytiwrpvtjdwsssahupoyyjveedgqsthefdyxvjweaimadykubntfqcpbjyqbtnunuxzyytxfedrycsdhkfymaykeubowvkszzwmbbjezrphqildkmllskfawmcohdqalgccffxursvbyikjoglnillapcbcjuhaxukfhalcslemluvornmijbeawxzokgnlzugxkshrpojrwaasgfmjvkghpdyxt")
Prints:
Step 18: Left pointer is at 18 and Right pointer is at 20
Palindromeness start: 17 - Palindromeness end: 20
Window length: 2
Before: Left is 0 and Right is 1
After: Left is 18 and Right is 20
String: xx
##################################################
Step 25: Left pointer is at 24 and Right pointer is at 27
Palindromeness start: 23 - Palindromeness end: 27
Window length: 3
Before: Left is 18 and Right is 20
After: Left is 24 and Right is 27
String: ibi
##################################################
Step 462: Left pointer is at 460 and Right pointer is at 464
Palindromeness start: 459 - Palindromeness end: 464
Window length: 4
Before: Left is 24 and Right is 27
After: Left is 460 and Right is 464
String: pppp
##################################################
Happy Coding! ( ˆ_ˆ )
