【回溯+双指针算法题记录】回文字符串汇总

验证回文串

题目🔗

题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

题目分析

这题主要问题在于包含非字母/数字字符，比如：' '、','、':'等，所以我们要把这些情况考虑进去。

cpp代码

class Solution {
public:bool isPalindrome(string s) {int i = 0;int j = s.size()-1;while(i < j){while(i < j && !(isdigit(s[i]) || isalpha(s[i]))) i++;while(i < j && !(isdigit(s[j]) || isalpha(s[j]))) j--;if(tolower(s[i]) == tolower(s[j])){i++; j--;}else return false;}return true;}
};

这里用了几个C库函数，方便我们处理：

1. isdigit(x)：判断x是否是数字；
2. isalpha(x)：判断x是否是字母；
3. tolower(x)：将大写字母转换成小写字母（如果本身是非字母字符则不变）。

131. 分割回文串

题目🔗

题目描述

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

题目分析

其实切割问题和组合问题本质上是一样的，我们将int startIndex当作上一次的分割结束点，横向是从startIndex到i这个区间切割的可能情况，纵向是针对每一种可情况的startIndex到i切割，再从i+1开始向后分割，即i+1就是上一次的分割结束点。

每次分割时可以判断当前startIndex到i是不是回文字符串，如果是，则将当前分割结果放入path中，如果不是就continue，去看下一个startIndex到i。

cpp代码

class Solution {
public:vector<string> path;vector<vector<string>> result;bool isPalindrome(string s, int i, int j) {// int i = 0;// int j = s.size()-1;while(i < j){while(i < j && !(isdigit(s[i]) || isalpha(s[i]))) i++;while(i < j && !(isdigit(s[j]) || isalpha(s[j]))) j--;if(tolower(s[i]) == tolower(s[j])){i++; j--;}else return false;}return true;}void backtracking(int startIndex, const string& s){// 终止条件if(startIndex >= s.size()){ // 当startIndex超出s大小，则放结果result.push_back(path);return;}for(int i = startIndex; i < s.size(); i++){if(isPalindrome(s, startIndex, i)){ // 如果当前切割是回文串string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);}else continue;backtracking(i + 1, s);path.pop_back();}}vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(0, s);return result;}
};