LeetCode-131 分割回文串

📝题目

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

示例:

输入: "aab"

输出:
[
  ["aa","b"],
  ["a","a","b"]
]

📝思路

第一次系统地学习回溯法，这类题大多可以套模板：

# main 函数调用 backtrack()

result = []
def backtrack(路径, 选择列表):
    if 满⾜结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

重点是如何表示递归过程，这里搬运一位大佬的图解：

📝题解

vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    track(res, s, {});
    return res;
}

//这里可以进一步优化为记忆化搜索
bool isPalindrome(const string& s) {
    if (s.length() == 0)    return true;
    int lft = 0, rgt = s.length()-1;
    while (lft < rgt) {
        if (s[lft] != s[rgt])   return false;
        lft++;
        rgt--;
    }
    return true;
}

void track(vector<vector<string>>& res, string s, vector<string> trackList) {
    if (s.length() == 0) {
        res.push_back(trackList);
        return;
    }

    for (int i = 1; i <= s.length(); i++) {
        if (isPalindrome(s.substr(0, i))) {
            trackList.push_back(s.substr(0, i));
            track(res, s.substr(i), trackList);
            trackList.pop_back();
        }
    }
}