[리트코드] 5. Longest Palindromic Substring

리트코드 5번 문제.

난이도: Medium

 

문제

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

A string is called a palindrome string if the reverse of that string is the same as the original string.

주어진 string에서 가장 긴 palindrome을 찾아야 한다. palindrome은 string을 거꾸로 해도 같은 string이 되는 경우를 말한다.

 

예시

Example 1

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

Example 2:

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

 

답

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check_palindrome(left, right):
            while(0 <= left and right < len(s) and s[left] == s[right]):
                left -= 1
                right += 1
            return left + 1, right - 1
        
        best_so_far = ""
        
        for i in range(len(s)): #1
        	# center가 i인 경우
            left, right = check_palindrome(i, i)
            len_substr = right - left + 1
            if len(best_so_far) < len_substr: 
                best_so_far = s[left: right + 1]
        	
            # center가 i와 i + 1 사이인 경우
            left, right = check_palindrome(i, i + 1)
            len_substr = right - left + 1
            if len(best_so_far) < len_substr: 
                best_so_far = s[left: right + 1]
        return best_so_far

Time Complexity: O(n^2)

 

설명

string이 palindromic substring (이하 PS) 인지 확인하는 가장 쉬운 방법은 string 가운데부터 양 옆으로 하나씩 확인해 나가는 방식이다. 이 가운데를 center라고 한다면 string 전체에서 center가 될 수 있는 곳은 2n - 1곳이 된다. 왜 n이 아니냐? 왜냐하면 center는 특정 index가 될 수도 있지만두 index 사이가 될 수도 있기 때문이다. 예를 들어 aba의 center는 b이지만 abba의 center는 b와 b사이이다.

 

먼저 check_palindrome 헬퍼 함수를 만들어서 주어진 left, right index에서 가장 긴 PS를 리턴하게 한다. 위에서 설명한 것 처럼 PS를 체크하는 방법은 string의 가운데 indices (left, right) 이 주어졌을때 양 옆으로 하나씩 가면서 확인해 나가는 것이다. 

 

#1에서 for loop를 생성해서 string 내의 가장 긴 PS를 확인한다. 또 best_so_far 이라는 변수를 생성한다. 이 변수는 for 루프가 돌아가면서 발견한 가장 긴 PS를 keep track 할 것이다.

 

#1의 for 루프 내에서는 center가 i인 경우와 center가 i 와 i + 1사이인 경우 두가지를 확인한다. check_panlindrome 헬퍼 함수를 이용하면 이 두가지 경우에서 가장 긴 PS를 리턴할 수 있다. check_palindrome에서 리턴된 두 인덱스를 이용해 best_so_far를 업데이트 한다. 

 

마지막으로 남은 best_so_far string이 input s의 PS이다. best_so_far를 리턴한다.