[코딩테스트] 리트코드(LeetCode) - Longest Palindromic Substring - Python, JS

문제

Given a string s, return the longest palindromic substring in s.

문자열 s가 주어졌을 때, 팰린드롬이 되는 가장 긴 부분문자열 리턴.

 

예시

1. 입력 s = "babad"

출력 "bab" 혹은 "aba"

2. 입력 s = "baad"

출력 "aa"

3. 입력 s = "a"

출력 "a"

 

=> 예시들에서 볼 수 있는 것은, 짝수개문자열, 혹은 한글자도 팰린드롬 취급을 하는 것이다.

 

조건

- s의 길이는 최대 1000.

 

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

 

풀이

LeetCode에는 다섯가지의 풀이 방법이 주어진다.

 

1. Longest Common Substring

- 주어진 문자열과, 이의 거꾸로된 버전에서

- 가장 긴, 공통적으로 나타나는 부분문자열 추출

 

예시:

s = "abad"일 때, 이의 거꾸로 된 버전은

s' = "daba"이다.

여기서 aba가 공통적으로 나타나므로, 이를 longest palindromic substring으로 생각.

 

=> 하지만 이 풀이는 틀린 풀이이다.

=> 다음과 같은 반례들이 있을 수 있기 때문.

 

예시:

s = "abacdfgdcaba"

s' = "abacdgfdcaba"

위와 같이 어떠한 문자열이 "mirrored"된 형태라면, 팰린드롬이 아닌데도 거꾸로된 문자열에도 나타날 수 있다.

 

2. Brute Force (무작정 풀기!)

- 주어진 문자열에서 추출가능한 모든 부분 문자열을, 팰린드롬이 맞는 지 체크하는 방법

 

예시:

s = "aba"일 때,

"a", "b", "a", "ab", "ba", "aba" 모두 체크

 

- 가능하지만, 효율성 테스트에서 통과 못한다.

 

- 어떠한 '부분 문자열'을 추출하는 행위는, s의 길이가 n이라고 했을 때,

n개 중에 2개 (시작 인덱스 i와 끝 인덱스 j)를 결정하는 행위

- 따라서 모든 부분문자열을 찾는 경우의 수는, nC2 = n * (n-1) / 2이다. => O(n^2)

- 각 문자열을 palindrome이 맞는 지 체크하는 행위는, 문자열의 문자 하나 하나를 살펴봐야 하므로 => O(n)

- 결국 종합적인 시간복잡도는 => O(n^3)

 

- s의 최대 길이가 1000이므로, n^3 = (1000)^3 = 1,000,000,000 혹은 1억으로 시간 제한에 걸린다.

 

- 참고: 프로그래머스 문제는 이 방법으로 통과가 가능하다.

piaflu.tistory.com/96

[코딩 테스트] 프로그래머스 - 가장 긴 팰린드롬 (Lv.3) in Python

 

3. 동적 계획법

- 어떠한 문자열이 주어졌을 때,

- 문자열의 맨 앞 글자와 맨 뒤 글자가 같고,

- 그 둘을 제외한 안쪽 문자열이 위와 같은 조건을 만족하면서,

- palindrome이 될 수 있는 base case에 해당된다면

- 그 문자열은 palindrome이다.

 

- 여기서 base case는

1. P(i, i) = true // 한 글자일 때 (ex. "a")

2. P(i, i+1) = (Si === S(i+1)) // 두 글자가 같을 때  (ex. "aa")

이다.

 

- 위와 같은 재귀 함수 혹은 점화식으로 풀어낼 수 있으므로, 동적 계획법을 사용하면 됨.

 

-

시작 인덱스 i와 끝 인덱스 j를 순회하면서 T/F를 볼테니, 2차원 배열을 저장해야하고, 따라서 공간 복잡도는 O(n^2).

 

- 시간 복잡도 또한 최대 n개의 i, 최대 n개의 j를 살펴봐야 하므로 O(n^2).f

 

4. Expand Around Center (중간을 중심으로 펼쳐나가기)

- 3번의 동적계획법과 풀이방식은 비슷하지만,

- 공간 복잡도 개선에 도움되는 풀이이다.

 

- 큰 문자열 -> 작은 문자열로 가지 말고,

- base case가 되는 작은 문자열 -> 큰 문자열로 검사하는 방법.

 

- 각 인덱스 i에서

- s[i:i+1] (한 글자), 혹은 s[i:i+2] (두 글자)가 palindrome인 지 검사하고,

- 맞다면 그 부분문자열의  하나 왼쪽과 하나 오른쪽의 글자들이 같은 지 검사

- 같다면 그 만큼의 부분문자열 또한 palindrome.

 

  - 이렇게 푼다면, 중심이 되는 base case의 가짓수

    n개 (한 글자)

    (n - 1)개 (두 글자)

    => 총 (2n-1)개에,

- 각각의 경우 expandAroundCenter가 최대 n개를 돌 수 있으므로

    => 시간 복잡도 O(n^2)

 

- 반면 변수 몇개만 저장하고 업데이트 하면 되므로 공간복잡도는 O(1)이 된다.

 

 

- 참고: 같은 풀이를 JS로 한다면 이렇게

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

const longestPalindrome = function(s) {
    let maxLen = -1;
    if (s.length < 1){
        return answer;
    }
    
    const n = s.length;
    let start = 0, end = 0;
    for (let i = 0;i<n;i++){
        len1 = expandAroundCenter(s, i, i);
        len2 = expandAroundCenter(s, i, i+1);
        maxLen = Math.max(len1, len2);
        if (maxLen > end - start){
            start = i - Math.floor((maxLen - 1)/2);
            end = i + Math.floor((maxLen) /2);
        }
    }
    return s.slice(start,end+1);
};

 

5. Manacher's Algorithm

- 이 특정한 문제를 O(n)에 풀 수 있는 알고리즘이다.

- 배우고 싶다면 여기로... en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm

Longest palindromic substring - Wikipedia

 

 

 

틀린 부분이 있다면 지적 부탁드립니다. 감사합니다.