# 132 - Palindrome Partitioning II

## 解法一 - 暴力法

``````class Solution {
public:
int minCut(string s) {
return findMinCut(s, 0, s.length()-1);
}

private:
int findMinCut(string& s, int start, int end) {
// if s is empty or s is palindrome, minCut == 0
if(start >= end || isPalindrome(s, start, end))
return 0;

// the maximal number of cut == the number of all length-1 pieces
int minCut = end-start;

// finetune 到這樣會過，但我不太懂為何不是
// for(int I=start+1; i<end; i++)
for(int i=start; i<=end; i++) {
if(isPalindrome(s, start, i)) {
minCut = min(minCut, 1+findMinCut(s, i+1, end));
}
}

return minCut;
}

bool isPalindrome(string& s, int i, int j) {
while(i < j) {
if(s[i++] != s[j--])
return false;
}

return true;
}
};
``````

## 解法二 - 暴力法 + memoization

``````class Solution {
public:
int minCut(string s) {
vector<vector<int>> memo(s.length(), vector<int>(s.length(), -1));
vector<vector<int>> memoIsPalindrome(s.length(), vector<int>(s.length(), -1));
return findMinCut(memo, memoIsPalindrome, s, 0, s.length()-1);
}

private:
int findMinCut(vector<vector<int>>& memo, vector<vector<int>>& memoIsPalindrome, string& s, int start, int end) {
// if s is empty or s is palindrome, minCut == 0
if(start >= end || isPalindrome(memoIsPalindrome, s, start, end))
return 0;

// the maximal number of cut == the number of all length-1 pieces
if(memo[start][end] == -1) {
int minCut = end-start;
for(int i=start; i<=end; i++) {
if(isPalindrome(memoIsPalindrome, s, start, i)) {
minCut = min(minCut, 1+findMinCut(memo, memoIsPalindrome, s, i+1, end));
}
}

memo[start][end] = minCut;
}

return memo[start][end];
}

bool isPalindrome(vector<vector<int>>& memoIsPalindrome, string& s, int i, int j) {
int x=i, y=j;
if(memoIsPalindrome[i][j] == -1) {
memoIsPalindrome[i][j] = 1;
while(x < y) {
if(s[x++] != s[y--]) {
memoIsPalindrome[i][j] = 0;
break;
}
}
}

return memoIsPalindrome[i][j] == 1;
}
};
``````

Runtime: 316 ms, faster than 19.07% of C++ online submissions for Palindrome Partitioning II. Memory Usage: 35.3 MB, less than 40.00% of C++ online submissions for Palindrome Partitioning II.

## 解法三 - DP

``````class Solution {
public:
int minCut(string s) {
// isPalindrome[i][j] == true if s[i] - s[j] is a palindrome
vector<vector<bool>> isPalindrome(s.length(), vector<bool>(s.length(), false));

// every string with one character is a palindrome
for (int i = 0; i < s.length(); i++) {
isPalindrome[i][i] = true;
}

// build isPalindrome table
for (int start = s.length() - 1; start >= 0; start--) {
for (int end = start + 1; end < s.length(); end++) {
if (s[start] == s[end]) {
// if it's a two character string or if the remaining string is a palindrome too
if (end-start == 1 || isPalindrome[start+1][end-1]) {
isPalindrome[start][end] = true;
}
}
}
}

// now lets populate the second table, every index in 'cuts' stores the minimum cuts needed
// for the substring from that index till the end
vector<int> cuts(s.length(), 0);
for (int start = s.length() - 1; start >= 0; start--) {
int minCuts = s.length()-start; // maximum cuts

for (int end = s.length() - 1; end >= start; end--) {
if (isPalindrome[start][end]) {
// we can cut here as we got a palindrome
// also we dont need any cut if the whole substring is a palindrome
minCuts = (end == s.length() - 1) ? 0 : min(minCuts, 1 + cuts[end+1]);
}
}

cuts[start] = minCuts;
}

return cuts[0];
}
};
``````