5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

最長回文子字串。

1. 列出所有子字串：

    `
    for i in range(length, 0, -1):
        for j in range(0, length -i+1): 
    `

2. 看是否回文：
   candidate == candidate[::-1]

Time: O(nˆ2), Space: O(n)

class Solution:    
    def longestPalindrome(self, s: str) -> str:
        if not s:return
        length = len(s) 
        # worst case it is T:O(n^2) S:O(n)
        for i in range(length, 0, -1):
            for j in range(0, length -i+1): 
                candidate = s[j:j+i] # 所有可能子字串
                if candidate == candidate[::-1]: # 是回文的
                    return candidate # 回傳
print(Solution().longestPalindrome('babad'))

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)