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

考察的知识点：递归、回溯；

解答方法分析：

1. 定义名为isPalindrome的辅助函数，用来判断一个字符串是否为回文串。通过两个指针从字符串的两端向中间进行比较，如果对应位置的字符不相等，则不是回文串。
2. 定义名为backtrack的辅助函数，用来进行回溯操作。该函数有三个参数，分别为当前处理的字符串s结果集res，以及临时列表temp。
3. 如果字符串s为空，表示已经将当前的分组方案添加到了结果集中，将临时列表temp添加到结果集res中，并返回。
4. 对于非空字符串s，遍历所有可能的切割起始位置i，从1到s的长度。
5. 获取从起始位置i开始的子串sub，然后判断sub是否为回文串。
6. 如果是回文串，则将sub加入临时列表temp中，并对剩余部分递归调用backtrack函数。
7. 递归调用完成后，将刚刚加入临时列表的子串移除，继续遍历下一个起始位置，进行下一次回溯。
8. 在主函数partition中，初始化结果集res和临时列表temp，然后调用backtrack函数。
9. 最后，对结果集res进行升序排序，并返回结果。

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    bool isPalindrome(string s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s[i] != s[j])
                return false;
            i++;
            j--;
        }
        return true;
    }

    void backtrack(string s, vector<vector<string>>& res, vector<string>& temp) {
        if (s.empty()) {
            res.push_back(temp);
            return;
        }

        for (int i = 1; i <= s.length(); i++) {
            string sub = s.substr(0, i);
            if (isPalindrome(sub)) {
                temp.push_back(sub);
                backtrack(s.substr(i), res, temp);
                temp.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> temp;
        backtrack(s, res, temp);
        sort(res.begin(), res.end());
        return res;
    }
};