[LeetCode > Medium > 5] Longest Palindromic Substring

문제

• https://leetcode.com/problems/longest-palindromic-substring/description/
• Runtime: 4614ms, Memory 16.34MB
• 주어진 문자열의 부분 문자열 중 가장 긴 회문을 반환

내 풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        result = s[0]
        length = len(s)
		
        # 2개의 포인터로 모든 경우의 수를 탐색
        for i in range(length):
            for j in range(i+1, length):
                # 현재 결과값보다 작으면 pass
                if j-i+1 <= len(result):
                    continue
                ss = s[i:j+1]
                
                # 회문이 맞는지 확인
                if ss == ss[::-1]:
                    result = ss
        
        return result

• 시간 복잡도
  • s의 길이가 n이라면, O(n³)
  • 1 <= n <= 1000
  • ( i의 for문 n ) * ( j의 for문 최대 n-1 ) * (  [i:j+1]에서 최대 n + [::-1]에서 최대 n ) 

참고 사항

• 슬라이딩 윈도우로 풀이 가능
  • 0 ~ n-1까지의 반복하는 인덱스와 우측으로 1칸, 2칸 이동한 인덱스을 가지고 있는다.
  • 인덱스와 이동한 인덱스을 투 포인터로 둔다.
  • 인덱스와 이동한 인덱스에 위치한 값이 같다면, 인덱스는 왼쪽으로 이동, 이동한 인덱스는 오른쪽으로 이동
    • 이동하고 비교하는 위 과정을 반복해 가장 긴 회문을 찾는다.