代码随想录二刷｜回溯｜分割回文串-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录二刷｜回溯｜分割回文串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

131.分割回文串

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

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

示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

解题思路

回溯三部曲

递归函数参数
全局变量数组path存放切割后回文的子串，二维数组result存放结果集

参数还需要startIndex，因为切割过的地方不能重复切割。
```
vector<string> path;
vector<vector<string>> result;
void backtracking(const string& s, int startIndex) 
```
递归函数终止条件
当切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。

在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
```
void backtracking (const string& s, int startIndex) {
	// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了。
	if (startIndex >= s.size()) {
		result.path_back(path);
		return;
	}
}
```

单层搜索的逻辑
在循环中定义了起始位置startIndex，那么[startIndex, i]就是这个要截取的子串。

首先判断这个子串是不是回文，如果是回文，就加入到vector<string> path中，path用来记录切割过的回文子串。

for (int i = startIndex; i < s.size(); i++) {
	if (isPalindrome(s, startIndex, i)) { // 如果是回文子串
		// 获取[startIndex, i]在 s 中的子串
		string str = s.substr(startIndex, i - startIndex + 1);
		path.push_back(str);
	} else { // 如果不是则直接跳过
		continue;
	}
	backtracking(s, i + 1); // 寻找i + 1为起始位置的子串
	path.pop_back(); // 回溯过程，弹出本次已经添加的子串
}

接下来判断回文子串，使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就找到了回文字符串。文章来源地址https://www.toymoban.com/news/detail-821771.html

bool isPalindrome(const 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;
}

代码实现

class Solution {
private:
	vector<vector<string>> result;
	vector<string> path;
	void backtracking(const string& s, int startIndex) {
		if (startIndex >= s.size()) {
			result.push_back();
			return;
		}
		for (int i = startIndex; i < s.size(); i++) {
			if (isPalindrome(s, startIndex, i)) {
				string str = s.substr(startIndex, i - stratIndex + 1);
				path.push_back(str);
			} else {
				continue;
			}
			backtracking(s, i + 1);
			path.pop_back();
		}
	}
	bool isPalindrome(const 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;
	}
public:
	vector<vector<string>> partition(string s) {
		result.clear();
		path.clear();
		backtracking(s, 0);
		return result;
	}
};