LeetCode_Palindrome Partitioning

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"]
  ]

　　DFS 求解全解神器

class Solution {
public:
    bool isPalindrome(const string &s, int start, int end)
    {
        assert(start< len && end < len) ;
        if(start > end) return false ;
        while(start < end)
        {
            if(s[start] != s[end])
                return false;
                
            start++;
            end --;    
        }    
        return true;
    }
    void DFS(const string &s,int start, vector<string> p)
    {
        if(start == len) {
            result.push_back(p);
            return ;
        }
        
        for(int i = start; i< len ; i++)
        {
            if(isPalindrome(s,start, i))
            {
                p.push_back(s.substr(start, i - start +1));
                DFS(s, i+1, p);
                p.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        result.clear();
        len = s.size();
        
        if(len == 0) return result;
        vector<string> p;
        DFS(s, 0, p);
        
        return result ;
    }
private:
    int len ;
    vector<vector<string>>  result;
};