[leetcode #132] Palindrome Partitioning II

Problem

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.

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

Constraints:

・ 1 <= s.length <= 2000
・ s consists of lower-case English letters only.

Idea

가장 어려워하는 Palindrome 문제가 나왔다. 그동안 Palindrome 문제가 나올 때마다 isPalindrome이라는 함수를 만들어 string 내 문자를 비교하는 방식 (O(n))으로 어찌어찌 문제를 풀어왔는데, 이 문제는 그렇게 풀면 Time Limit Exceeded에 걸릴게 뻔했다. 분명히 dp를 써서 string의 palindrome 여부를 두 번 확인하는 일은 없어야 하는게 명확하지만 머리가 영 돌아가지 않는다. Map을 써서 각 character의 위치를 list로 저장해 보기도 했지만 코드가 너무 길고 복잡해 중간에 포기하고야 말았다. 결국 두 시간 정도 머리를 꽁꽁 싸매다 다른 사이트에서 어떻게 풀었는지 참조할 수밖에 없었다🥲.

Time Limit에 안 걸리려면 dp가 필수인데 여기선 두 가지 값을 dp로 저장해야 한다.

첫 번째, substring이 palindrome인지 여부를 저장해야 한다.
두 번째, starting index가 0인 substring이 palindrome으로 나눠지기 위한 최소값을 저장해야 한다. (문제를 더 작은 문제로 나눈다.)

그럼 substring이 palindrome인지 어떻게 확인해야 할까?

1. 문자열의 길이가 1이면 palindrome이다.
2. 문자열의 길이가 2이고 문자열을 이루는 문자들이 같으면 palindrome이다.
3. 문자열의 길이가 3이상일 때, 첫번째 문자(ith)와 마지막 문자(jth)가 같으면 i+1부터 j-1까지의 substring이 palindrome이면 palindrome이다.

위 아이디어에 착안해 isValid라는 2-d array를 만들고 row는 string의 시작 index, column은 마지막 index로 하여 palindrome 여부를 저장한다. substring의 길이는 1부터 전체 string의 길이까지 순차적으로 계산하면 palindrome 여부를 계산할 수 있다.

Palindrome인지 확인할 수 있다면 문제가 원하는 값을 구하기 위해 더 작은 문제부터 풀어본다. palindrome 여부를 확인할 때와 달리 두 번째 dp는 주어진 문자열의 시작점이 동일한 substring만 고려하면 된다. (startingIndex = 0) substring의 길이가 n일때, dp를 계산하는 방법은 다음과 같다.

1. substring이 palindrome이면 dp[n] = 0
2. 문자열이 나눠지는 지점을 k라 하고 k부터 n까지 substring이 palindrome일 때, dp[n] = min(dp[n], dp[k-1]+1)

2와 같은 결론이 나오는 이유는 dp[k-1]이 0부터 k-1까지의 substring이 palindrome으로 나눠지는 최소값이고 k부터 n까지 substring이 palindrome이므로 dp[k-1]에 1을 더한 값이 dp[n]이 되기 때문이다. k를 0부터 n까지 반복한다고 하면 결국엔 문자열의 길이가 1인 palindrome까지 도달하게 된다. 탐색하는 동안 dp[n]은 계속 바뀌게 되지만 항상 min값을 저장하므로 우리가 원하는 값을 구하는 데는 문제가 없다.

Solution

class Solution {
    public int minCut(String s) {
    	int n = s.length();
        boolean[][] isValid = new boolean[n][n];

	# 1. palindrome 여부 저장
        for (int len=1; len <= n; len++) {
            for (int i=0; i <= n-len; i++) { // i = startIndex
            	int j = i + len - 1; // j = endIndex
            	if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2)
                    	isValid[i][j] = true;
                    else {
                    	isValid[i][j] = isValid[i+1][j-1];
                    }
                }
            }
        }

	# 2. palindrome으로 나누는 최소값 저장
    	int[] dp = new int[n];
    	Arrays.fill(dp, n);
    	for (int len=1; len <= n; len++) {
            for (int k=0; k < len; k++) {
            	if (isValid[k][len-1]) {
                    if (k == 0) {
                    	dp[len-1] = 0;
                    	break;
                    }
                    dp[len-1] = Math.min(dp[len-1], dp[k-1]+1);
                }
            }
        }

	return dp[n-1];
    }
}    

풀이를 이해하고 나니 그동안 palindrome 문제를 풀고 다른 풀이를 안 봤던 게 후회가 되었다. 이렇게 효율적으로 푸는 방법이 있는데 그동안 문제 푸는 것에만 집중하고 더 나은 방법이 있는데도 외면한 셈 아닌가. 다른 사람들의 코드리뷰는 외면하고 돌아가는 코드를 어찌어찌 짜놓는 거랑 다를 바가 없다. 앞으로 리트코드 문제를 풀면 다른 풀이 방법도 쓱 훑어보고 좋은 아이디어를 얻을 수 있도록 해야겠다.

글로만 풀이를 쓰니 나조차도 이해하기가 어려워 그림을 그리고 싶은데 내가 가진 아이패드는 애플펜슬2와 호환이 안 되어 아이패드도 신형을 사야 하나 고민중 =_=

Reference

https://leetcode.com/problems/palindrome-partitioning-ii/
https://anj910.medium.com/leetcode-132-palindrome-partitioning-ii-5aa8916c536f