Longest Palindromic Substring - leetcode(5)

Longest Palindrome

요구사항

• Given a string s, return the longest palindromic substring in s.
  => 문자열 s가 주어지면 s에서 가장 긴 팰린드롬을 반환한다.

Palindrome(회문) 이란

거꾸로 읽어도 제대로 읽는것과 같은 문장, 낱말, 숫자 등 문자열이다.

Solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        result = ""
        resultLength = 0
        
        #해당 사항이 없을 경우 빠르게 return한다.
        if len(s) < 2 or s == s[::-1]:
            return s
            
        for i in range(len(s)):
            # odd length
            left, right = i, i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if (right - left + 1) > resultLength:
                    result = s[left:right+1]
                    resultLength = right - left + 1
                left -= 1
                right += 1

            # even length
            left, right = i, i +1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                if (right - left + 1) > resultLength:
                    result = s[left:right + 1]
                    resultLength = right - left + 1
                left -= 1
                right += 1

        return result
        
sol = Solution()

print(sol.longestPalindrome(preInput))
# >>> "bab"

📌 코드 풀이

1. 결과를 넣을 변수와, 결과의 길이를 넣을 변수를 만들어 준다.
2. 문자가 2글자 미만이거나 이미 팰린드롬인 경우 바로 return하여 함수를 종료한다.
3. for i in range(len(input))로 반복문을 돌려주고 내부에서 left, right = i, i 로 만들어 준다.
   => left와 right가 pointer역할을 하게된다.
4. left가 0보다 크고 right가 문자열 길이보다 작고 left, right를 입력 받은 문자열의 인덱스로 넣었을때 동일하다면 포인터를 확장시키면서 팰린드롬인지 확인한다.
5. right - left + 1이 현재 결과의 길이보다 크다면 결과와 결과의 길이를 업데이트 해준다.
6. 그 뒤 left -= 1 / right += 1 로 포인터를 넓혀가며 팰린드롬을 확장해 나간다.
   => 여기서 input[left] == input[right]가 다르다면 팰린드롬이 아니기 때문에 while이 끝나게 되고 다시 반복문을 돌며 더 긴 팰린드롬을 확인하는 것이다.

아래와 같이 포인터를 늘려가며 팰린드롬을 찾는다.

leetcode

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