# Palindrome Partitioning II

## Question

Given a string s, cut s into some substrings such that
every substring is a palindrome.

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

Example
For example, given s = "aab",

Return 1 since the palindrome partitioning ["aa","b"] could be produced
using 1 cut.


## 题解1 - 仅对最小切割数使用动态规划

### Python

class Solution:
# @param s, a string
# @return an integer
def minCut(self, s):
if not s:
print 0

cut = [i - 1 for i in xrange(1 + len(s))]

for i in xrange(1 + len(s)):
for j in xrange(i):
# s[j:i] is palindrome
if s[j:i] == s[j:i][::-1]:
cut[i] = min(cut[i], 1 + cut[j])
return cut[-1]


### 源码分析

1. 当 s 为 None 或者列表为空时返回0
2. 初始化切割数数组
3. 子字符串的索引位置可为[0, len(s) - 1], 内循环 j 比外循环 i 小，故可将 i 的最大值设为1 + len(s) 较为便利。
4. 回文的判断使用了[::-1] 对字符串进行反转
5. 最后返回数组最后一个元素

## 题解2 - 使用动态规划计算子字符串回文状态

### Python

class Solution:
# @param s, a string
# @return an integer
def minCut(self, s):
if not s:
print 0

cut = [i - 1 for i in xrange(1 + len(s))]
PaMatrix = self.getMat(s)

for i in xrange(1 + len(s)):
for j in xrange(i):
if PaMatrix[j][i - 1]:
cut[i] = min(cut[i], cut[j] + 1)
return cut[-1]

def getMat(self, s):
PaMat = [[True for i in xrange(len(s))] for j in xrange(len(s))]
for i in xrange(len(s), -1, -1):
for j in xrange(i, len(s)):
if j == i:
PaMat[i][j] = True
# not necessary if init with True
# elif j == i + 1:
#     PaMat[i][j] = s[i] == s[j]
else:
PaMat[i][j] = s[i] == s[j] and PaMat[i + 1][j - 1]
return PaMat


### C++

class Solution {
public:
int minCut(string s) {
if (s.empty()) return 0;

int len = s.size();
vector<int> cut;
for (int i = 0; i < 1 + len; ++i) {
cut.push_back(i - 1);
}
vector<vector<bool> > mat = getMat(s);

for (int i = 1; i < 1 + len; ++i) {
for (int j = 0; j < i; ++j) {
if (mat[j][i - 1]) {
cut[i] = min(cut[i], 1 + cut[j]);
}
}
}

return cut[len];
}

vector<vector<bool> > getMat(string s) {
int len = s.size();
vector<vector<bool> > mat = vector<vector<bool> >(len, vector<bool>(len, true));
for (int i = len; i >= 0; --i) {
for (int j = i; j < len; ++j) {
if (j == i) {
mat[i][j] = true;
} else if (j == i + 1) {
mat[i][j] = (s[i] == s[j]);
} else {
mat[i][j] = ((s[i] == s[j]) && mat[i + 1][j - 1]);
}
}
}

return mat;
}
};


### Java

public class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) return 0;

int len = s.length();
int[] cut = new int[1 + len];
for (int i = 0; i < 1 + len; ++i) {
cut[i] = i - 1;
}
boolean[][] mat = paMat(s);

for (int i = 1; i < 1 + len; i++) {
for (int j = 0; j < i; j++) {
if (mat[j][i - 1]) {
cut[i] = Math.min(cut[i], 1 + cut[j]);
}
}
}

return cut[len];
}

private boolean[][] paMat(String s) {
int len = s.length();
boolean[][] mat = new boolean[len][len];

for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
if (j == i) {
mat[i][j] = true;
} else if (j == i + 1) {
mat[i][j] = (s.charAt(i) == s.charAt(j));
} else {
mat[i][j] = (s.charAt(i) == s.charAt(j)) && mat[i + 1][j - 1];
}
}
}

return mat;
}
}