문제 설명

Longest Palindromic Substring - LeetCode

주어진 문자열 s에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제입니다.
✅ 팰린드롬(Palindrome)이란?

  • 앞에서 읽어도, 뒤에서 읽어도 동일한 문자열
  • 예: "racecar", "madam", "a"

✅ 제약 조건

  • 1 ≤ s.length ≤ 1000
  • 반환값: 가장 긴 팰린드롬 부분 문자열

해설

1️⃣ 다이나믹 프로그래밍 (DP, O(N²))

  • DP 테이블을 사용하여 s[i:j+1]이 팰린드롬인지 저장
  • dp[i][j] = True → s[i:j+1]이 팰린드롬
  • 점화식:
    • s[i] == s[j]이고,
    • j - i <= 2 (길이 2 이하) 또는 dp[i+1][j-1] == True 이면,
    • dp[i][j] = True
  • 시간 복잡도: O(N²) → 테이블 갱신이 O(N²)

2️⃣ 확장 중심 접근법 (Expand Around Center, O(N²))

  • 각 문자를 중심으로 팰린드롬 확장 (중심 확장)
  • 홀수 길이 팰린드롬: "racecar" → 중심 e
  • 짝수 길이 팰린드롬: "abba" → 중심 bb
  • 시간 복잡도: O(N²) → 각 문자를 중심으로 O(N) 확장

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1  # 가장 긴 팰린드롬의 시작 위치와 길이

    # 길이 1짜리 문자열은 항상 팰린드롬
    for i in range(n):
        dp[i][i] = True

    # 길이 2 이상 문자열 검사
    for j in range(1, n):
        for i in range(j):
            if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]):  
                dp[i][j] = True
                if j - i + 1 > max_length:  # 더 긴 팰린드롬이면 갱신
                    start, max_length = i, j - i + 1

    return s[start:start + max_length]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def longestPalindrome(s: str) -> str:
    if len(s) < 2:
        return s

    def expand_around_center(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]  # 범위를 넘어간 부분을 제외

    longest = ""
    for i in range(len(s)):
        odd_palindrome = expand_around_center(i, i)  # 홀수 길이
        even_palindrome = expand_around_center(i, i + 1)  # 짝수 길이
        longest = max(longest, odd_palindrome, even_palindrome, key=len)

    return longest

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

var longestPalindrome = function(s) {
    if (s.length < 2) return s;

    const expandAroundCenter = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return s.slice(left + 1, right);
    };

    let longest = "";
    for (let i = 0; i < s.length; i++) {
        let oddPalindrome = expandAroundCenter(i, i);   // 홀수 길이
        let evenPalindrome = expandAroundCenter(i, i+1); // 짝수 길이
        longest = oddPalindrome.length > longest.length ? oddPalindrome : longest;
        longest = evenPalindrome.length > longest.length ? evenPalindrome : longest;
    }

    return longest;
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform