가장 긴 부분 회문 찾기 palindrome

회문이란 왼쪽부터 읽는 것과 오른쪽부터 읽는 것이 같은 문자를 뜻한다.

ex) 기러기, 토마토, aba, abba, aa, a 등등...

 

 

가장 긴 부분 회문이란

"babad"에서 "bab"와 "aba"이고

"cbbd"에서 "bb"이다.

 

 

회문의 특성을 생각해보면 회문 안에 회문이 있다는 것을 찾을 수 있다. 이를테면,

"cabbac"는 "abba"를 포함하고 있고

"abba"는 "bb"를 포함하고 있으며

"bb"는 "b"를 포함하고 있다.

이를 보면 다음과 같은 생각을 가질 수 있다.

1. 양쪽 끝에 있는 문자들이 서로 같고

2. 양쪽 끝에 있는 문자를 제외한 글자가 회문이면

3. 해당 글자는 회문이다.

 

(ex. "abba"일 때

1. 양쪽 끝에 있는 문자들이("abba") 서로 같고

2. 양쪽 끝에 있는 문자를 제외한 글자가("abba") 회문이면

3. 해당 글자는 ("abba")는 회문이다.

단, 글자가 2개일 때는 양쪽 끝에 있는 글자만 서로 같으면 회문이며 글자가 1개인 것은 조건 없이 모두 회문이다.

 

따라서 state(start, end)라는 함수가 s[start, end]가 회문임을 확인하는 함수일 때 다음과 같이 작성하면 될 것이다.

start = end = 0 일 때 state(start, end) is True (ex. "a")

start = 0, end = 1일 때 state(start, end) is True if s[start] = s[end] (ex. "aa")

start = 0, end = 2일 때 state(start, end) is True if s[start] = s[end] and state(start + 1, end - 1) (ex "aba")

start = 0, end = 3일 때 state(start, end) is True if s[start] = s[end] and state(start + 1, end - 1) (ex "abba")

...

 

 

이를 Python3 코드로 나타내면 다음과 같다.

def solution(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    palindrome_start, palindrome_len = 0, 1
    
    # 길이가 1인 문자들 (ex. "a")은 모두 회문이다.
    for i in range(n):
        dp[i][i] = True

    for end in range(0, n):
        for start in range(end - 1, -1, -1):
            if s[start] == s[end]:
                # 길이가 2일 때는 (ex. "aa") s[start] == s[end] 이기만 해도 회문이다.
                # 길이가 3이상일 때는 (ex. "aba") s[start] == s[end] 이면서 dp[start+1][end-1]이 True여야 회문이다.
                if end - start == 1 or dp[start+1][end-1]:
                    dp[start][end] = True
                    tmp_palindrome_len = end - start + 1

                    if palindrome_len < tmp_palindrome_len:
                        palindrome_start = start
                        palindrome_len = tmp_palindrome_len

    return s[palindrome_start: palindrome_start + palindrome_len]

 

위 코드는 2차원 배열 dp를 생성하므로 공간 복잡도가 O(N^2)이다.

포인터를 사용하면 공간 복잡도 O(1)으로 해당 문제를 해결할 수 있다.

순서는 다음과 같다.

1. right를 증가시켜가며 s[i]와 달라지는 부분을 찾고 s[i, right - 1]을 한다. (ex. "aabb"에서 "aa"를 찾는 것)

2. left = i -1 로 세팅하고 양쪽 끝에 있는 문자들이 서로 같은지 확인한다. 같다면 left -= 1, right +=1을 하고 틀려질 때까지 돌린다.

3. right - left + 1을 해서 회문의 길이를 확인하고 palindrome_len보다 크면 업데이트한다. 

 

def solutuon(s: str):
    n = len(s)
    palindrome_start, palindrome_len = 0, 1

    for i in range(0, n):
        right = i
        while right < n and s[i] == s[right]:
            right += 1

        left = i - 1
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1

        tmp_palindrome_len = right - left - 1
        if tmp_palindrome_len > palindrome_len:
            palindrome_len = tmp_palindrome_len
            palindrome_start = left + 1

    return s[palindrome_start: palindrome_start + palindrome_len]

 

 

 

 

 

 

---

관련 문제 - https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

https://leetcode.com/problems/palindromic-substrings/

Palindromic Substrings - LeetCode

 

문제 풀이 해설 - https://leetcode.com/problems/longest-palindromic-substring/discuss/151144/Bottom-up-DP-Two-pointers

Bottom-up DP / Two pointers - LeetCode Discuss