leetcode131-分割回文串 回溯与方便判断回文串的的判断表

131. 分割回文串

这是看了卡尔的代码写出来的

class Solution {
public:
    int size;
    vector<vector<string>> res;
    vector<string> path;
    bool isHuiwen(string s,int start,int end)
    {
        for(int i=start,j=end;i<j;i++,j--)
        {
            if(s[i]!=s[j])  return false;
        }
        return true;
    }
    void backTracking(string s,int startNum)
    {
        if(startNum==size)
        {
            res.push_back(path);return;
        }
        for(int i=startNum;i<size;i++)
        {
            if(isHuiwen(s,startNum,i))
            {
                string str = s.substr(startNum,i-startNum+1);
                path.push_back(str);
            }
            else continue;  //从这里开始就已经不是回文串了，后面的就不必判断了，直接进入下一轮；
            backTracking(s,i+1);
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        size=s.size();
        backTracking(s,0);
        return res;
    }
};

时间复杂度主要都用于重复判断回文串了。

因此可以创建一个size*size大小的表，【i】【j】表示【i , j 】是否为回文串。有点像动态规划。

void computePalindrome(const string& s) {
        // isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串 
        isPalindrome.resize(s.size(), vector<bool>(s.size(), false)); // 根据字符串s, 刷新布尔矩阵的大小
        for (int i = s.size() - 1; i >= 0; i--) { 
            // 需要倒序计算, 保证在i行时, i+1行已经计算好了
            for (int j = i; j < s.size(); j++) {
                if (j == i) {isPalindrome[i][j] = true;}
                else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);}
                else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);}
            }
        }
    }