## Tuesday, November 25, 2014

### [LeetCode] Palindrome Partitioning I, II

Palindrome Partitioning I

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = `"aab"`,
Return
```  [
["aa","b"],
["a","a","b"]
]```

Palindrome Partitioning II

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.
For example, given s = `"aab"`,
Return `1` since the palindrome partitioning `["aa","b"]` could be produced using 1 cut.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33``` ```class Solution { public: vector> partition(string s) { int n = s.size(); vector> ret; vector sol; vector> isPal(n, vector(n,false)); for(int i=n-1; i>=0; i--) { for(int j=i; j=j-1 || isPal[i+1][j-1]) && s[i]==s[j]) isPal[i][j] = true; } } findPartitions(s, 0, isPal, sol, ret); return ret; } void findPartitions(string &s, int start, vector> &isPal, vector &sol, vector> &ret) { if(start==s.size()) { ret.push_back(sol); return; } for(int i=start; i

DP[i] = min (DP[j] + 1) ，对所有 0<=j<i，且s[j: i-1]为palindrome。

https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25``` ```class Solution { public: int minCut(string s) { int n = s.size(); if(n<=1) return 0; vector> isPal(n, vector(n, false)); for(int i=n-1; i>=0; i--) { for(int j=i; jj-1 || isPal[i+1][j-1]) && s[i]==s[j]) isPal[i][j] = true; } } vector dp(n+1,INT_MAX); dp[0] = -1; for(int i=1; i<=n; i++) { for(int j=i-1; j>=0; j--) { if(isPal[j][i-1]) { dp[i] = min(dp[i], dp[j]+1); } } } return dp[n]; } }; ```