代码随想录算法训练营第二十三天-回溯算法-131. 分割回文串

• 对字符串的分割，就是字符串下标的遍历
• 下标就是分割标记
• 这个题目的神奇之处就是它毫无特色，可以用以前几乎一模一样的回溯框架代码来套用
• 但也就是看似与回溯毫无关联，但可以完美适用回溯代码，本身就是神奇所在

#include <iostream>
#include <vector>class Solution {
private:std::vector<std::string> path;std::vector<std::vector<std::string>> result;bool isPalindrome(const std::string& str, int start, int end) {for (int i = start, j = end; i < j; ++i, --j)if(str[i] != str[j])return false;return true;}void backtracking(const std::string& str, int startIndex) {if (startIndex >= str.size()) {result.push_back(path);return;}for (int i = startIndex; i < str.size(); ++i) {if (isPalindrome(str, startIndex, i)) {std::string sub_str = str.substr(startIndex, i - startIndex + 1);path.push_back(sub_str);} elsecontinue;backtracking(str, i + 1);path.pop_back();}}
public:std::vector<std::vector<std::string>> partition(std::string s) {backtracking(s, 0);return result;}
};

• 汇总