Leetcode|分割|131. 分割回文串（组合first索引）

SL_World

发布于 2021-09-18 16:13:09

20600

代码可运行

文章被收录于专栏：XX

运行总次数：0

代码可运行

1 回溯法（first索引）

做这类题之前不要慌，也不要直接上手code，先把简例决策树的图画出来，然后一气呵成写代码基本就能一次AC

【注意】：函数传参使用引用&来节省内存的不止vector能操作，只要是容器都有传引用的省内存的需求，string也不要忘了

class Solution {
    int size;
    vector<vector<string>> solution;
    vector<string> path;
public:
    bool notValid(string& str) {
        int n = str.size();
        for (int i = 0; i < n / 2; i++) 
            if (str[i] != str[n - 1 - i]) return true;   
        return false;
    }
    void backtrack(string& str, int first, int len) {
        if (len == size) {   // 换成if (first >= size)一样成立
            solution.emplace_back(path);
            return;
        }
        // 1.first索引
        for (int i = first; i < size; i++) {   
            string subStr =  str.substr(first, i - first + 1);
            // 2.判断满足回文串的条件
            if (notValid(subStr)) continue;
            path.emplace_back(subStr);
            backtrack(str, i + 1, len + subStr.size());
            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        size = s.size();
        backtrack(s, 0, 0);
        return solution;
    }
};