leetcode : palindrome partitioning II

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

Palindrome Partitioning II - LeetCode

 

리트코드에서 난이도 Hard인 Dynamic Programming 문제로, 이 문제는 DP를 이용해서 O(n^2)으로 풀어야 한다.

 

일단 이전글을 봤으면 문자열에서 O(n^2)으로 모든 palindrome을 찾아내는 방법은 알게 되었을 것이다.

https://keep-your-pace.tistory.com/13

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

 

 

남은 작업은 문자열과 길이가 같은 DP 배열을 만들고 문자열을 left-to-right scan하면서 DP배열을 채워나가는 것이다. 이 문제가 왜 DP 문제일까? 일단 palindrome을 찾는 과정 자체는 당연히 dp이다. 기존의 연산결과를 재활용해 새로운 정보를 얻을 수 있기 때문. ( i < j이고 string[i]==string[j]이고 string[i+1:j]가 palindrome이면 string[i:j+1]역시 palindrome이다 )

palindrome을 partitioning 하는 minimum cut을 찾는 과정 역시 dp인 이유는 다음과 같다.

위처럼 문자열 중간의 영역이 palindrome이라는 것을 발견했다고 치자 (빨간 영역)

이 영역의 첫 글자 인덱스는 left이고 마지막 글자 인덱스는 right라고 가정.

이때 

앞 부분의 파란 영역의 minimum cut을 알고있다면,

(파란영역 + 빨간영역)의 minimum cut은 파란영역의 minimum cut + 1로 새로 계산해 볼 수 있다. (빨간 영역과 파란 영역을 나눠야 하므로 cut 하나가 추가될거고 +1 한것이다)

 

그리고 기존에 알던 (빨간영역+파란영역)의 minimum cut이랑 새로 계산해 본 값을 비교해서 더 작은 값을 배정하면 되는것이다.

만약에

 

위와같이 앞부분이 없는 경우 (left가 0인 경우)라면 빨간 영역의 minimum cut은 0이 된다. 전체가 palindrome이니까.

 

이걸 코드로 어떻게 나타낼까?

일단 길이 N(문자열 길이)의 dp 배열을 만든다.

dp[i]의 의미는 문자열 인덱스 0부터 i까지의 영역의 palindrome partitioning minimum cut이다.

그러니까 dp를 다 수행하고 나면 정답은 dp[N-1]이 되는 것이다.

 

dp배열은 0,1,2,3,4..와 같이 초기화 해야 한다.

최악의 경우 palindrome이 하나도 없어서 한글자 한글자 partitioning해야되기 때문에 그 worst case인 경우의 minimum cut으로 배열을 초기화 해주고 새로 계산된 값이 더 작으면 바꿔나가는 방식이다. (worst case보다 minimum cut이 커질 순 없으니까)

dp = [i for i in range(N)]

 

그리고 left to right 스캔을 해가면서

for right in range(N):

 

그 내에 있는 모든 palindrome에 대해서 (이전 포스팅을 참고해서 isPalindrome배열은 이미 완성됐다고 가정)

for left in range(right+1):
        if isPalindrome[left][right]:

 

위에 그림 설명에서 파란영역이 없는 경우 (left == 0)랑 아닌 경우를 나눠서 dp배열값을  갱신시켜준다

if left == 0:
      dp[right] = 0
else:
      dp[right] = min(dp[right], dp[left-1] + 1)

 

dp = [i for i in range(N)]
for right in range(N):
    for left in range(right+1):
        if isPalindrome[left][right]:
            if left == 0:
                dp[right] = 0
            else:
                dp[right] = min(dp[right], dp[left-1] + 1)

 

이렇게 하면 정답을 구할 수 있다.

 

전체 코드는 다음과 같다.

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 or isPalindrome[left+1][right-1]:
                isPalindrome[left][right] = True

dp = [i for i in range(N)]
for right in range(N):
    for left in range(right+1):
        if isPalindrome[left][right]:
            if left == 0:
                dp[right] = 0
            else:
                dp[right] = min(dp[right], dp[left-1] + 1)

print(dp[N-1])

 

그런데 굵은 글씨 친 부분을 잘보면 같은 조건이라는 것을 알 수 있다

그리고 바깥쪽 반복문이 right, 안쪽 반복문이 left라는 것도 똑같다

그래서 이 두 개의 이중반복문을 합칠 수 있다. 이렇게

 

string = "abaddccc"

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

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

                if left == 0:
                    dp[right] = 0
                else:
                    dp[right] = min(dp[right], dp[left-1] + 1)


print(dp[N-1])

 

이렇게 해서 오늘도 dp 한 문제를 풀었다!! dp 고수가 되는 그날까지~~