题解 | #所有的回文子串I#

考察知识点：回溯

题目分析：

可以使用回溯法找到所有的回文子串。就是把给定的字符串分割成一个一个的回文串，可以通过回溯的方法将字符串一段一段分隔，判断每一个子串是否是回文子串。如果是回文串则找包含下一个元素的回文子串，直到原字符串结尾。

首先将该串的第一个位置作为起始位置，不断地枚举结束位置。找到满足条件的结束位置后，就需要从下一个元素开始（下一个子串必须包含该元素），找剩下的区间中满足条件的回文串集合。下图中group的目的是找满足条件的每一种情况，将每种情况加入到结果集中就得到了题目的解。

每次遇到分出来的字符串不是回文串的情况时，就不必再向下走了。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector<vector<>>
     */
    bool isPalindrome(string &s, int start, int end) {
        int left = start, right = end; 
        while (left < right) {
            if (s[left++] != s[right--]) 
                return false;
        }
        return true;
    }
    void backtrack(string &s, int start, vector<string> &group, vector<vector<string>> &groups) {
        if (start == s.size()) {
            groups.push_back(group);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            if (isPalindrome(s, start, i)) {
                group.push_back(s.substr(start, i - start + 1));
                backtrack(s, i + 1, group, groups);
                group.pop_back();
            }
        }
    }
    vector<vector<string> > partition(string s) {
        // write code here
        vector<vector<string>> groups;
        vector<string> group;
        backtrack(s, 0, group, groups);
        return groups;
    }
};