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

验证回文串

题目🔗

题目描述

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

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

给你一个字符串 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;
    }
};