5. Longest Palindromic Substring

문자열의 부분중 가장 긴 회문 찾기 문제이다. 

Dynamic Programming(이하 DP)으로 많이 풀지만, 이번에는 window sliding기법을 이용해서 풀어보자. 

사실 DP로 푸는 것은 잘 이해가 되지 않았다..

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

아이디어는 이렇다. 

현재 위치를 중심으로 양 옆을 늘려가면서 회문인지 확인하는 것이다. 

 

ex) 'abac'에서 위치를 찾아보자. 두번째 'b'의 위치에서 보자

b를 중심으로 양 옆에 'a'가 있고, 'aba'는 회문이 된다. 

 

하지만 이 아이디어에서 조심해야될것이 중심을 홀수, 짝수를 구분해야된다는 것이다.

 

이유는 홀수, 짝수 일때 중심이 달라지기때문이다.

 

    def longestPalindrome(self, s: str) -> str:
        def searchPalindrome(left, right):
            length = len(s)
            
            # 범위 확인과 양쪽 끝값이 같으면 범위 확장
            while left >=0 and right < length and s[left] == s[right]:
                left -= 1
                right += 1
            # 마지막에 확장한 범위를 하나 줄여서 값을 구한다.
            return s[left+1:right]

        # 들어온 입력값이 2 이하이면 회문을 구할 필요도 없지!
        if len(s)<2:
            return s
        result = ""
        for i in range(len(s)):
            # 홀수 
            s1 = searchPalindrome(i,i)
            # 짝수
            s2 = searchPalindrome(i,i+1)
            
            # 더 긴 것을 채택 
            if len(result) < len(s1):
                result = s1
            if len(result) < len(s2):
                result = s2
        return result