LeetCode-分割回文串（C++）

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

思路：本题用回溯算法，具体可参考代码随想录。首先定义全局变量result为结果集，path保存切割好的回文子串。

对于示例1，for循环横向遍历，在aab中先截取a，然后截取aa，然后aab。递归纵向遍历，在截取a的下面在截取a，截取ab；在截取aa的下面截取b；aab下面没有可以截取的，终止。然后继续递归。

在截取子串的过程中判断子串是否是回文子串，是就加入路径，不是就跳出，继续下一个。

回溯算法三部曲：

1. 确定回溯函数参数和返回值：参数为字符串s和递归遍历的起始位置startIndex，返回类型为void。
2. 确定终止条件：当startIndex大于等于s的大小时，说明切割完毕，将path加入结果集，return。
3. 确定单层回溯逻辑：定义起始位置startIndex，截取子串[startIndex, i] ，首先判断这个子串是不是回文，如果是回文，就加入在path中，不是就跳出。然后递归，递归起始位置为i+1，因为切割过的不能重复切割。然后回溯，撤销之前加入path的子串。

代码：

class Solution {	//131. 分割回文串
public:
	vector<vector<string>> result;
	vector<string> path;
	bool isPalindrome(string letter) {
		if (letter.size() == 1)return true;
		int left = 0;
		int right = letter.size() - 1;
		while (left < right) {
			if (letter[left] != letter[right]) return false;
			left++;
			right--;
		}
		return true;
	}
	void backtracking(string const& s, int startIndex) {
		if (startIndex >= s.size()) {
			result.push_back(path);
			return;
		}
		for (int i = startIndex; i < s.size(); ++i) {
			string str = s.substr(startIndex, i - startIndex + 1);
			if (isPalindrome(str)) {
				path.push_back(str);
			}
			else continue;
			backtracking(s, i + 1);
			path.pop_back();
		}
	}
	vector<vector<string>> partition(string s) {
		backtracking(s, 0);
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35