[LeetCode] 5. Longest Palindromic Substring

5. Longest Palindromic Substring

Medium

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

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

---

문제 풀이

문제 접근

1. s 문장의 글자 크기는 1000 이기 때문에 모든 조건을 다 확인해봐도 시간초과가 되지 않을 것 같다. 

풀이

1. Palindrom 단어는 두가지 케이스가 존재한다.
2. 가운데 인덱스에서 양쪽으로 퍼지는 경우.
3. 각 두개 인덱스에서 양쪽으로 퍼지는 경우가 있다. 
4. 0 부터 문장의 끝까지 모두 검색하면서, 두가지 케이스를 모두 확인한다. 

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        self.res_cnt = 0
        self.res = ''
        def check(l, r, s, ans):
            while l >= 0 and r < len(s):
                if s[l] != s[r]:
                    break
                ans += 2
                l -= 1
                r += 1
            if ans > self.res_cnt:
                self.res_cnt = ans
                self.res = s[l + 1 : r]
        for i in range(len(s)):
            check(i - 1, i + 1, s, 1)
            check(i, i + 1, s, 0)
        return self.res