代码随想录二刷 ｜回溯 ｜分割回文串

题目描述

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(); // 回溯过程，弹出本次已经添加的子串
  }
  

  接下来判断回文子串，使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就找到了回文字符串。

  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;
	}
};