Problem Link:
http://oj.leetcode.com/problems/palindrome-partitioning-ii/
We solve this problem by using Dynamic Programming.
Optimal Sub-structure
Assume a string S has the palindrome minimum cuts n, and S = W1 + W2 + ... + Wn where Wi is a palindrome. Then for S' = W1 + W2 + ... + Wn-1, S' must have the palindrome minimum cut n-1. It is easy to prove by the contradiction.
Recursive Formula
Given a string s, let A[0..n-1] be an array where A[i] is the palindrome minimum cuts for s[0..i]. The recursive formula for A[] is:
A[0] = 0, since an empty string is a palindrome
For i > 0, we have
A[i] = 0, if s[0..i] is a palindrome
A[i] = min{ A[j]+1 | j = 1, ..., i and s[j+1..i] is a palindrome }, otherwise
Implementation
The following code is the python impelmentation accepted by oj.leetcode.com
class Solution:
# @param s, a string
# @return an integer
def minCut(self, s):
"""
Let A[0..n-1] be a new array, where A[i] is the min-cuts of s[0..i]
A[0] = 0, since "" is a palindrome
For i > 0, we have
A[i] = 0, if s[0..i] is palindrome
A[i] = min{ A[j]+1 | 0 < j <= i }, otherwise
"""
n = len(s)
# n = 0 or 1, return 0, no cut needed
if n < 2:
return 0 # Initialization: s[0..i] at least has i cuts to be partitioned into i characters
A = range(n)
for i in xrange(n):
A[i] = i # Compute P: P[i][j] = True if s[i..j] is a palindrome
P = [None] * n
for i in xrange(n):
P[i] = [False] * n for mid in xrange(n):
P[mid][mid] = True
# Check strings with mid "s[mid]"
i = mid - 1
j = mid + 1
while i >= 0 and j <= n-1 and s[i]==s[j]:
P[i][j] = True
i -= 1
j += 1
# Check strings with mid "s[mid]s[mid+1]"
i = mid
j = mid + 1
while i >= 0 and j <= n-1 and s[i] == s[j]:
P[i][j] = True
i -= 1
j += 1 # Quick return, if s[0..n-1] is a palindrome
if P[0][n-1]:
return 0 # DP method, update A from i = 1 to n-1
for i in xrange(n):
if P[0][i]:
A[i] = 0
else:
for j in xrange(i):
if P[j+1][i]: # s[0..i] = s[0..j] + s[j+1..i], where s[j+1..i] is a palindrome
A[i] = min(A[i], A[j]+1) return A[n-1]