131 Palindrome Partitioning [Leetcode]

题目内容：

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的方法。先穷举所有回文分支下的每个分支所有的状况，再添加到结果中去，再回溯回上一个节点。

代码实现，时间8ms：

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> temp;
        backTracking(s, , result, temp);
        return result;
    }

    void backTracking(string &s, int index, vector<vector<string>> &result, vector<string> &temp) {
        if(index >= s.size()) {
            result.push_back(temp);
            return;
        }

        for(int i = index; i < s.size(); ++i) {
            if(isPalindrome(index, i, s)) {
                temp.push_back(s.substr(index, i-index+));
                backTracking(s, i+, result, temp);
                temp.pop_back();//backtrack
            }
        }
    }

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