[파이썬 알고리즘 인터뷰] 5. 가장 긴 팰린드롬 부분 문자열

https://github.com/onlybooks/algorithm-interview

GitHub - onlybooks/algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는

1. 문제

5. Longest Palindromic Substring

가장 긴 팰린드롬 부분 문자열을 출력하라

팰린드롬: 뒤집어도 같은 내용인 것 ex) "aba", "aaaaa"

 

2. 내 풀이

def longestPalindrome(self, s: str) -> str:
    for i in range(len(s)):
        for j in range(i + 1):
            temp = s[j:len(s) - i + j]
            if temp == temp[::-1]:
                return temp

Brute Force 방식을 사용해서 가능한 모든 부분 문자열을 선택하고, 선택한 부분이 팰린드롬인지 확인했다. 그리고 가장 긴 팰린드롬을 찾아야 하기 때문에 부분 문자열 중에서는 길이가 긴 것을 먼저 선택했다. 시간복잡도는 O(n^3)이다.

 

3. 중앙을 중심으로 확장하는 방법

def longestPalindrome(self, s: str) -> str:

    #팰린드롬 판별 및 투포인터 확장
    def expand(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]

    #해당 사항이 없을 때 빠르게 리턴
    if len(s) < 2 or s == s[::-1]:
        return s

    result = ''
    #슬라이딩 윈도우 우측으로 이동
    for i in range(len(s) - 1):
        result = max(result, expand(i, i + 1), expand(i, i + 2), key = len)

    return result

이 풀이 방법은 포인터를 이용해서 문자열을 처음부터 끝까지 탐색한다. 그리고 두개 혹은 세개의 문자로 이루어진 팰린드롬이 발견된다면 해당 팰린드롬의 앞, 뒤 문자를 하나씩 확인하면서 최장 팰린드롬을 찾는다. O(n^2)의 시간복잡도를 가진다.

 

4. Dynamic Programing(동적 프로그래밍)을 이용한 방법

동적 프로그래밍이란 큰 문제를 여러개의 작은 문제로 나누어서 해결하고, 작은 문제를 풀었던 값을 저장해두고 재사용하는 방법이다. 지난 포스팅에서 다루었던 피보나치 수열을 O(n)의 시간복잡도로 구하는 방법도 동적 프로그래밍의 한 종류이다.

https://baechu-story.tistory.com/9?category=991646

 

[C] 시간복잡도가 O(n)인 재귀함수로 피보나치 수열 구하기

"bab"라는 문자열이 팰린드롬이고, 이 문자열에 양쪽에 "a"가 추가되어 만들어진 "ababa"도 팰린드롬이다. 이 문제를 풀 때는 이처럼 팰린드롬 양쪽에 같은 문자가 추가되면 그 역시도 팰린드롬이라는 점을 이용한다. 먼저 모든 경우의 수로 부분 문자열을 만들어 각 문자열이 팰린드롬인지 확인한다. 이 과정에서 해당 문자열이 팰린드롬인지 여부를 배열에 저장하고,  길이가 4 이상인 문자열이 나타나면 양쪽 끝 문자가 같은지, 양쪽 끝을 제외한 문자가 팰린드롬인지를 배열에서 확인한다. 이 두가지 조건이 맞다면 해당 문자열을 팰린드롬이라고 판단하고 배열에 저장한다. 이 방법은 O(n^2)의 시간복잡도를 가진다.

/* 자바를 이용한 풀이 */
public String longestPalindrome(String s) {

    if (s == null || "".equals(s)) {
        return s;
    }

    int len = s.length();

    String ans = "";
    int max = 0;

    boolean[][] dp = new boolean[len][len];

    for (int j = 0; j < len; j++) {

        for (int i = 0; i <= j; i++) {

            boolean judge = s.charAt(i) == s.charAt(j);

            dp[i][j] = j - i > 2 ? dp[i + 1][j - 1] && judge : judge;

            if (dp[i][j] && j - i + 1 > max) {
                max = j - i + 1;
                ans = s.substring(i, j + 1);
            }
        }
    }
    return ans;
}