[leetcode] 132. Palindrome Partitioning II

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

---

문자열 s가 주어지면 s를 잘라 부분문자열들을 만들었을 때 모든 부분문자열들이 펠린드롬이 되는 최소 절단횟수를 구하여라.

---

 먼저 DP로 2차원 배열을 만들어 펠린드롬[i][e] = 문자열[i,e]가 펠린드롬인지를 구한다.

펠린드롬[i][j] = 펠린드롬[i+1][j-1] (s[i] == s[j])
             = false (s[i] != s[j])

문자열[i~j]은 문자열의 첫문자와 끝 문자가 다르면 false,

첫문자와 끝문자가 같다면 문자열[i+1, e-1]이 펠린드롬인 경우는 펠린드롬, 아니면 펠린드롬이 아니다.

 

위 점화식으로 펠린드롬 여부를 구하면 이번엔 1차원 배열을 만든다.

dp[i] = s[0~i] 의 모든 파티션 문자열들이 펠린드롬이 되는 최소 절단횟수.

 

문자열 "aab"로 예를 들어보자.

펠린드롬[i][j]	0	1	2
0	1	1	0
1	1	1	0
2	1	1	1

dp 배열을 채우기 위해서는 펠린드롬 배열이 필요하므로 위에서 말한 점화시으로 펠린드롬 2차원 배열을 채우면 위와 같은 표를 구할 수 있다.

dp[0] : s[0~0] = "a" 는 펠린드롬이기 때문에(펠린드롬[0][0] = true) 절단하지 않아도 펠린드롬을 만들 수 있다. 따라서 최소절단횟수는 0.

dp[1] : s[0~1] = "aa"는 펠린드롬이기 때문에(펠린드롬[0][1] = true) 절단하지 않아도 펠린드롬을 만들 수 있다. 따라서 최소절단횟수는 0.

dp[2] : s[0~2] = "aab"는 펠린드롬이 아니기 때문에 인덱스를 탐색하면서 탐색중인 인덱스를 절단하면서 가능한 절단횟수를 모두 구해본다. 이 때, 절단한 뒤의 문자열은 펠린드롬임을 보장해야 하며, 앞의 문자열은 펠린드롬이 아니어도 dp 배열로 최소절단횟수를 가져올 수 있으므로 펠린드롬을 만들 수 있음을 이용한다. 

  i) "a", "ab"로 분리 : "ab"는 펠린드롬이 아니기 때문에 펠린드롬을 만들 수 없다.

  ii) "aa", "b"로 분리 : "b"는 펠린드롬이기 때문에 dp[1] (문자열 "aa"를 펠린드롬화 하기 위한 최소 절단 횟수) 0 에 이번에 분리하기 위한 절단 횟수 1을 더한 1이 절단횟수이다.

  가능한 모든 절단 문자열들의 탐색이 끝났을 때, 구한 최소 절단횟수인 1이 dp[2]가 된다.

i	0	1	2
dp[i]	0	0	1

위 dp 배열을 모두 채우면 dp[n-1]인 1이 정답이 된다. (n = 문자열 s 길이)

 

시간복잡도는 O(N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/132.%20Palindrome%20Partitioning%20II.cpp