Python Algorithm Q6
Q6 longest-palindromic-substring
Q
Given a string s, return the longest palindromic substring in s.
Sample Input
Input: s = “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Input: s = “cbbd”
Output: “bb”
Input: s = “a”
Output: “a”
Input: s = “ac”
Output: “a”
Constraints
- 1 <= s.length <= 1000
- s consist of only digits and English letters.
1. My Solution <- Given Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def longestPalindrome(self, s: str) -> str:
def expand(left: int, right: int) ->str:
while left >= 0 and right < len(s) and s[left]==s[right]:
left-=1
right+=1
#when escaped from the while loop, this array has much more index than palindrome.
#ZXXXXY condition or XXXXY (left is - index) or ZXXXX (right exceeds the length)
#therefore returns the index "left+1", and "right"(in string slicing, :right returns until right-1 index)
return s[left+1:right]
if len(s) < 2 or s==s[::-1]: #filtering - single letter or whole palindrome
return s
result = '' #gen blank string
for i in range(len(s)-1):
result = max(result,
expand(i, i+1), #abbc : even number two pointer
expand(i, i+2), #axyxc : odd number two pointer
key=len #the criteria for checking which is max is length of the string
)
return result
#for testing
a = Solution()
s = "babad"
print(a.longestPalindrome(s))
Refering the comment while following the explanation. This function consists of two center code chunk.
The first one is expand funcion. What expand function do is to return the string that is palindrome. This takes two factors, left and right. It starts to expand until not palinrome(or reached the edge of the string, begin and end). You need to be aware of the return string. When it escaped from the while loop, it means that now string has some problem. So returns the string “just before” escaped from loop, “left+1:right”
The second one is the way expand function used. We need two types of “two pointer”, even one and odd one. Expand function is designed to expand ambidirectionally, so one object can describe only 1 3 5… or 2 4 6…. Therefore two kinds of two pointer is required. Compare from the first element to last element(=s[length-1]).
Let’s take when i=2 case for example(s=”babad”). i=3, so starts with ‘b’ expand(2, 3) and expand(2, 4) and previous max result is being compared.
- expand(2, 3) : ‘aba’ /next one ‘babad’ X -> ‘aba’
- expand(2, 4) : ‘ba’ X -> return s[3:4] == s[3] == ‘b’
- result : previous best fit answer when i=2, ‘bab’ (is also answer)
+in the middle of the code, “if len(s)~” is for filtering. This filters the sentence which is palindrome itself(Of course, it contains single letter).
Overall Review
Really complicated… This problem makes me so depressed. The longest… problem series are so difficult for me. It takes really much time to understand the codes. But I can learn so much from this problem. First, Divide & Conquer straetgy is almost always the answer. In this question, dividing roles, expanding and utilzing expand function, makes the problem quite simple. Don’t be frustrated by vague and inexplicit solution that you derived. Just divide and think separately.