[Python] 팰린드롬 알고리즘 (Palindrome Algorithm) 설명 및 예제

팰린드롬 알고리즘

 

안녕하세요. gaki 입니다.

오늘은 팰린드롬 알고리즘에 대해서 알아보겠습니다.

팰린드롬이란, 어떤 문자열을 거꾸로 뒤집었을때 원래의 문자열과 동일한 문자열을 의미합니다.

 

팰린드롬인 문자열들

 

<목차>

1. 팰린드롬 알고르즘 설명 - Two Pointer [time: O(N)]

2. 팰린드롬 알고리즘 응용 - DP 활용 [time: O(N^2)]

3. 팰린드롬 알고리즘 응용2 - Manacher's 알고리즘 [time: O(N)]

 

1. 팰린드롬 알고리즘 설명

---

팰린드롬 알고리즘은 말그대로 문자열이 팰린드롬인지 아닌지 구분하는 알고리즘 입니다.

예를들어 "RADAR" 라는 문자열이 있다고 합시다.

이 문자열은 거꾸로 뒤집어도 "RADAR" 이므로, 팰린드롬입니다.

그럼 어떤 문자열이 팰린드롬인지 알 수 있는 방법은 무엇이 있을까요 ?

 

먼저 two pointer 를 이용해서 풀 수 있습니다.

문자열의 맨 처음과 맨 끝에 포인터 1개씩을 각각 놔둔 뒤,

둘다 한칸씩 움직이면서 두 문자열이 같은지 비교하는 방법입니다.

 

s = "abcdcba"

head = 0
tail = len(s) - 1

while (head <= len(s) // 2):
	if (s[head] == s[tail]):
    	head += 1
        tail -= 1
   	else:
    	return False
return True

# 비슷한 방법
def check_palin(word):
    for i in range(len(word)//2):
        if word[i] != word[-(i+1)]:
            return False
    return True

 

2. 팰린드롬 알고리즘 응용 - DP 활용 

---

팰린드롬 알고리즘을 DP 를 활용해 풀 수도 있습니다.

이 경우에는 위의 경우와는 다르게, 어떤 문자열에서 팰린드롬인 서브스트링의 최대 길이를 뽑아내는 경우를 나타냅니다.

문자열 s 가 있을때, s[0] 과 s[-1] 이 같을 경우, s[1:-1] 이 팰린드롬이면, s 는 팰린드롬임을 알 수 있습니다.

즉, dp[0][0] 은 s[0:1] 을 나타냅니다. 

즉 dp[0][0] 이 True 라면, s[0:1] 은 팰린드롬이라는 뜻입니다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ret = ""
        dp = [[0] * len(s) for _ in range(len(s))]
        
        for i in range(len(s)):
            dp[i][i] = True;
            ret = s[i]
        
        
        for i in range(len(s)):
            for j in range(i-1, -1, -1):
                if s[i] == s[j]:
                    if i - j == 1 or dp[j+1][i-1] is True:
                        dp[j][i] = True
                        if (len(ret) < len(s[j:i+1])):
                            ret = s[j:i+1]
    
        return ret