131. Palindrome Partitioning

發表於 | 分類於

problem

solution

option 1 - dfs

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
class Solution {
public:
    vector<vector<string>> ret;
    bool isPalindrome(string s, int l, int r){
        while(l<r){
            if(s[l++] != s[r--]) return false;
        }
        return true;
    }
    void dfs(string s, int start, vector<string> & path){
        if(start==s.size()){
            ret.push_back(path);
        }
        
        for(int i=start;i<s.size() ; ++i){
            if(!isPalindrome(s, start,i)) continue;
            path.push_back(s.substr(start, i-start+1));
            dfs(s,i+1, path);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        vector<string> path;
        dfs(s, 0, path);
        return ret;
        
        
    }
};

option 2 - dp