# palindrome partitioning

## palindrome partitioning

### Brute-force DFS

Enumerate every substring in string s, if it's a palindrome, dfs the rest string. If we get the end of the string, push the list back to the result.

`````` 1 class Solution {
2 private:
3 vector< vector < string > > result;
4 public:
5     vector<vector<string>> partition(string s) {
6         result.clear();
7         vector< string > v;
8         DFS(s,0,v);
9         return result;
10     }
11     void DFS( string s, int start, vector< string >& v ) {
12         int l = s.length();
13         if ( start == l ) {
14             result.push_back(v);
15             return;
16         }
17         for ( int i = start; i < l; i++ ) {
18             string sub = s.substr(start,i-start+1);
19             if ( isPalindrome(sub) ) {
20                 v.push_back(sub);
21                 DFS(s,i+1,v);
22                 v.pop_back();
23             }
24         }
25     }
26     bool isPalindrome(string s) {
27         int l = s.length();
28         for ( int i = 0; i < (l+1)/2; i++ ) {
29             if ( s[i] != s[l-1-i] ) {
30                 return false;
31             }
32         }
33         return true;
34     }
35 };``````

### Better way

Using spcae to save the time.`dp[i][j]` means wheter the string between i and j is palindrome. Then DFS.

`````` 1 class Solution {
2 private:
3     vector< vector < string > > result;
4     int dp[1000][1000];
5 public:
6     vector<vector<string>> partition(string s) {
7         result.clear();
8         memset(dp,0,sizeof(dp));
9         DP(s);
10         vector< string > t;
11         DFS(s,0,t);
12         return result;
13     }
14     void DP( string s ) {
15         int l = s.length();
16         for ( int i = 0; i < l; i++ ) {
17             dp[i][i] = 1;
18             int j = min(i,l-1-i);
19             int k = 1;
20             while ( k <= j ) {
21                 if ( s[i-k] == s[i+k] ) {
22                     dp[i-k][i+k] = 1;
23                 } else {
24                     break;
25                 }
26                 k++;
27             }
28             j = min(i,l-2-i);
29             k = 0;
30             while ( k <= j ) {
31                 if ( s[i-k] == s[i+1+k] ) {
32                     dp[i-k][i+k+1] = 1;
33                 } else {
34                     break;
35                 }
36                 k++;
37             }
38         }
39     }
40     void DFS( string s, int x, vector< string >& v ) {
41         int l = s.length();
42         if ( l == x ) {
43             result.push_back(v);
44             return;
45         }
46         for ( int i = x; i < l; i++ ) {
47             if ( dp[x][i] ) {
48                 v.push_back(s.substr(x,i-x+1));
49                 DFS(s,i+1,v);
50                 v.pop_back();
51             }
52         }
53     }
54 };``````