[437] 팰린드롬 판별 & 부분 문자열 중 팰린드롬 찾기

1. 팰린드롬?

팰린드롬(palindrome)은 우리말로 회문(回文)이라고도 합니다.

거꾸로 읽어도 바르게 읽은 것과 같은 문장이나 단어를 뜻합니다.

팰린드롬과 관련된 다양한 알고리즘을 알아봅시다.

2. 팰린드롬 판별하기(문자열 비교)

문자열을 거꾸로 만들어 원래의 문자열과 비교합니다.

단순하고 직관적인 방법입니다.

파이썬으로 문자열을 거꾸로 만들 때는 slicing의 step을 -1로 사용하면 쉽습니다.

def is_palin(S):
    if S == S[::-1]:
        return True
    return False

print(is_palin("abcda"))
# False

print(is_palin("abcba"))
# True

 

조금 더 생각해보면 굳이 문자열 전체를 비교할 필요가 없다는 것을 알 수 있습니다.

문자열을 반으로 나누어 뒤쪽 반을 거꾸로 만들어 비교해도 가능합니다.

문자열의 길이가 홀수인지 짝수인지에 따라 slicing 할 때 범위에 주의합니다.

def is_palin(S):
    l = len(S)
    if S[:l//2] == S[:-(-l//2)-1:-1]: # 올림을 음수의 버림을 이용해 구현, math의 ceil을 사용해도 됨.
        return True
    return False

print(is_palin("abcda"))
# False

print(is_palin("abcba"))
# True

 

https://www.acmicpc.net/problem/13235

3. 팰린드롬 판별하기(투 포인터)

두 개의 포인터를 만들어 한 칸씩 가운데로 이동하며 글자를 비교합니다.

문자열을 slicing하지 않아도 되므로 그만큼 효율성이 좋습니다.

def is_palin(S):
    l, r = 0, len(S)-1
    while l < r:
        if S[l] != S[r]:
            return False
        l += 1
        r -= 1
    return True

print(is_palin("abcda"))
# False

print(is_palin("abcba"))
# True

투 포인터의 처음 위치만 조절하면 부분 문자열이 팰린드롬인지도 확인할 수 있기 때문에 자주 사용됩니다.

 

https://www.acmicpc.net/problem/10988

4. 부분 문자열 중 팰린드롬 찾기(완전 탐색)

주어진 문자열의 부분 문자열 중에 팰린드롬을 찾는 방법을 알아봅시다.

2중 for문을 통해 부분 문자열의 길이와 시작 위치를 바꿔가며 모든 부분 문자열을 찾습니다.

S = "abcde"
length = len(S)
for i in range(length): # 부분 문자열 길이
    for j in range(length-i): # 부분 문자열 시작 위치
        print(S[j:i+j+1]) # 부분 문자열 시작 위치 ~ 부분 문자열 길이만큼 slicing
# a
# b
# c
# d
# e
# ab
# bc
# cd
# de
# abc
# bcd
# cde
# abcd
# bcde
# abcde

예를 들어 "colossus"라는 문자열의 부분 문자열 중 팰린드롬은 "c", "o", "l", "s", "u", "ss", "olo", "sus"입니다.

2중 for문으로 찾은 모든 부분 문자열을 앞서 만든 투 포인터를 활용한 팰린드롬 판별 함수에 넣어 모든 팰린드롬을 찾을 수 있습니다.

시간복잡도는 2중 for문에 팰린드롬 판별 함수가 실행되므로 \(\mathbf{O(n^3)}\)이 됩니다.

S = "colossus"
length = len(S)

def is_palin(l, r):
    while l < r:
        if S[l] != S[r]:
            return False
        l += 1
        r -= 1
    return True

for i in range(length): # 부분 문자열 길이
    for j in range(length-i): # 부분 문자열 시작 위치
        if is_palin(j, i+j):
            print(S[j:i+j+1])
# c
# o
# l
# o
# s
# s
# u
# s
# ss
# olo
# sus

5. 부분 문자열 중 팰린드롬 찾기(동적 계획법)

부분 문자열이 팰린드롬인지 확인하는 과정에서 반복되는 과정이 생깁니다.

이를 효율적으로 해결하기 위해 다음과 같은 과정을 생각해볼 수 있습니다.

조건	내부 문자열이 팰린드롬이다.	내부 문자열이 팰린드롬이 아니다.
바깥 두 글자가 같다.	팰린드롬이다.	팰린드롬이 아니다.
바깥 두 글자가 다르다.	팰린드롬이 아니다.	팰린드롬이 아니다.

dp[i][j] 가 i번째 문자부터 j번째 문자까지의 부분 문자열이 팰린드롬인지 여부를 저장하고 있다면, 점화식은 다음과 같습니다.

dp[i][j] = dp[i+1][j-1] and (문자열[i] == 문자열[j])

2차원 dp 테이블을 채워가는 과정을 통해 모든 부분 문자열의 팰린드롬 여부를 알 수 있습니다.

따라서 시간복잡도는 \(\mathbf{O(n^{2})}\)입니다.

S = "colossus"
length = len(S)
dp = [[False]*length for _ in range(length)]

# 한 글자는 모두 팰린드롬
for i in range(length):
    dp[i][i] = True
    print(S[i])

# 두 글자는 서로 같으면 팰린드롬
for i in range(length-1):
    if S[i] == S[i+1]:
        dp[i][i+1] = True
        print(S[i:i+2])

# 이후에는 양 끝이 같고, 그 안쪽 부분 문자열이 팰린드롬이면 팰린드롬
for i in range(length-2):
    for j in range(i+2, length):
        if S[i] == S[j] and dp[i+1][j-1]:
            dp[i][j] = True
            print(S[i:j+1])
# c
# o
# l
# o
# s
# s
# u
# s
# ss
# olo
# sus

6. 부분 문자열 중 팰린드롬 찾기(Manacher's algorithm)

앞의 동적 계획법을 활용한 방법을 더 최적화하여 시간복잡도를 \(\mathbf{O(n)}\)으로 개선한 방법입니다.

자세한 내용은 아래의 위키와 별도의 포스팅을 참고해주세요.

https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm

Longest palindromic substring - Wikipedia