[leetcode] Longest Palindromic Substring / 투포인터

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def solve(left:int, right:int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left-1:right]
        result = '' 
        
        # 예외처리 코드 
        if len(s) < 2 or s == s[::-1]:
            return s
        
        for i in range(len(s)-1):
            result = max(result,
                         solve(i, i+1),
                         solve(i, i+2),
                        key = len)
        
        return result

투포인터를 활용하여 푼 문제! 
우선 예외처리를 한다

if len(s) < 2 or s == s[::-1]:
            return s

문자열 길이가 1이거나 현재 문자열과 뒤집은 문자열 (s[::-1])이 같은 경우 바로 문자열을 return 시킨다.  

투포인터를 활용하여 중간값부터 확장해나가는 구조이다. 
중간값은 for 문을 활용해서 0부터 len(s)-1 까지 지정해보고 하나씩 확인해본다. 그리고 문자열 길이가 가장 긴 값을 result 에 저장하며 갱신한다. 

투포인터 알고리즘 부분인 while문 안에서는 중간값부터 확장해 나가므로 while문 조건으로 
left >= 0 and right <= len(s)-1 이라고 표시했다
또한 left와 right 가 각각 가리키는 문자가 동일하면 포인터를 확장해나간다 

while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left-1:right]

마지막으로 펠린드롬 문자열의 길이는 홀수일 수도, 짝수일 수도 있다 -> 즉, 문자열이 증가할 때 앞 뒤로 하나씩 증가할 수도 있고, 앞 뒤로 두개씩 (짝수) 증가할 수도 있다는 의미이다 
두가지 모두 검토해야 하므로 solve(i, i+1), solve(i, i+2) 를 모두 확인한다.