I used to be graduate student in Chinese Academy of Sciences, Now I am a Ph.D. candidate in Tongji University. I am doing some work in Machine Learning and Computer Vision.
"""
5. Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
"""
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
ans = ""
# 枚举子串的长度 l+1
for l in range(n):
# 枚举子串的起始位置 i,这样可以通过 j=i+l 得到子串的结束位置
for i in range(n):
j = i + l
if j >= len(s):
break
if l == 0:
dp[i][j] = True
elif l == 1:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
if dp[i][j] and l + 1 > len(ans):
ans = s[i:j+1]
return ans
if __name__ == "__main__":
test = Solution()
inputS = ['aaabaaaba', 'acbaaa', 'aaa']
print(test.longestPalindrome(inputS[0]))
pass