LeetCode-131-分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

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

Code

//思路：利用DFS回溯，每次获取符合回文的字符串，加入到数组中，继续操作剩下的字符串
class Solution {
public:
    vector<vector<string>> partition(string s) {
        if(s.length()==0)return res;
        vector<string> _res;
        DFS(s,s.length(),_res);
        return res;
    }
    //回溯
    void DFS(string str,int length,vector<string> _res){
            if (length <= 0) {
                res.push_back(_res);
                return;
            }
            for (int i = 1;i <= length;i++) {
                string temp = str.substr(0, i);
                if(isPalindrome(temp,temp.length())){
                    _res.push_back(temp);
                    DFS(str.substr(i, length - i), length - i, _res);
                    //每次都得把前一次的回文串移除
                    //整个for循环只寻找当前层可能存在的回文串，找到并处理完当前回文的回溯逻辑需要
                    //删除，这样不会对同层下一次的迭代造成干扰
                    _res.pop_back();
                }
            }
    }
    //判断回文
    bool isPalindrome(string s,int length){
        if(length ==1)
            return true;
        for (int j = 0;j < length / 2;j++) {
            if (s[j] != s[length- 1 - j])
                  return false;
        }
        return true;
    }

private:
    vector<vector<string>> res;
};