문자열 속 모든 palindrome 찾아내기 (dynamic programming)

https://leetcode.com/problems/palindrome-partitioning-ii/

Palindrome Partitioning II - LeetCode

문제 내용

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

 

오늘도 아침에 평화롭게 leetcode에서 dp 문제를 찾아 풀던중 palindrome 관련 문제를 보게 되었다. 오랜만이다 palindrome!! Hard난이도의 문제를 풀고 있었는데 아무래도 이 문제는 여러 subproblem으로 나눠 풀어서 베이스를 쌓은 후 푸는게 좋겠다고 생각했다. 이 문제를 풀기 위한 subproblem 중 하나가 left-to-right one scan으로 모든 palindrome을 찾아내는 것이다. ( O(n^2) )

 

isPalindrome이라는 2차원 배열을 만들고

scan이 다 끝나고 나면

이 isPalindrome 배열에 모든 palindrome 정보가 들어있어야 한다.

가령 "dabaa"라는 문자열이 있다면

isPalindrome[1][3] = True이다. 문자열 인덱스 1인 부분부터 3인 부분까지 잘라보면 "aba"로 palindrome이기 때문이다.

이런 isPalindrome 배열을 one scan으로, O(n^2)으로 구현해야 한다.

 

다음은 "abaddccc"라는 문자열에 대해서 이 작업을 수행한 결과다

문자열 속 모든 palindrome을 찾아냈다. 중복되는 게 있는 것처럼 보이지만 사실 글자만 같을뿐 인덱스가 달라서 중복되는 palindrome은 아니다.

 

이제 방법을 알려줘

목표에 대해 충분히 설명을 한 것 같으니 이제 HOW를 살펴보도록 하자.

 

isPalindrome 관점에서 보면

1. isPalindrome[i][i] 는 True다. 한 글자기 때문이다. 한 글자는 당연히 palindrome이다.

2. isPalindrome[i][i+1] 두 글자인 경우는 두 글자가 같으면 palindrome이다. palindrome은 짝수인 경우랑 홀수인 경우를 나눠서 생각해야 돼서 골치 아픈데 생각보다 간단하게 해결할 수 있다.

3. 만약 palindrome인 문자열이 있으면 그 양끝에 같은 문자를 붙여도 palindrome이 된다. 이걸 반대로 얘기하면 양끝 문자가 같을 때 그 안쪽 문자열이 palindrome이면 그 문자열은 palindrome인것. 즉 string[i]와 string[j]가 같을 때 isPalindrome[i+1][j-1]이 True이면 isPalindrome[i][j]도 True라는 것.

 

코드 구현 관점에서 보면

기본적으로 이중 반복문을 이용.

바깥쪽 iteration의 변수는 right (문자열의 오른쪽 끝을 나타냄)

안쪽 iteration 변수는 left (문자열의 왼쪽 끝을 나타냄)

1. isPalindrome[right][right]는 당연히 True (한글자니까)

2. left를 0부터 right-1까지 iteration을 돈다.

   만약 string[left]가 string[right]와 같다면

       만약 right-left가 1이면 (두 글자면 짝수형 palindrome이다)

       아니면 string[left+1][right-1]이 palindrome인지 검사하고 맞으면 string[left][right]도 palindrome 판정을 한다

 

코드

string = "abaddccc"

N = len(string)
isPalindrome = [[False for _ in range(N)] for _ in range(N)]

for right in range(N):
    isPalindrome[right][right] = True
    for left in range(right):
        if string[left] == string[right]:
            if right-left == 1:
                isPalindrome[left][right] = True
            elif isPalindrome[left+1][right-1] == True:
                isPalindrome[left][right] = True

for i in range(N):
    print(isPalindrome[i])

for right in range(N):
    for left in range(right+1):
        if isPalindrome[left][right]:
            print(">>",string[left:right+1])