02 回文字符串

125 验证回文串 (opens new window)

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

输入一个字符串，输出一个布尔值表示该字符串是否为回文串

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

解析：

​ 回文串一般都可以采用双指针从两头向中间检验，或者采用中心扩展法从中间向两头验证是否为回文串。

​ 本题可以采用双指针的策略，从字符串首尾两端逐个字符检验。但是本题中给出的字符串有许多非字母字符，可以用一个新字符串保存原字符串中的所有字母小写形式，然后对其使用双指针方法验证。

class Solution {
public:
    bool isPalindrome(string s) {
        // 筛选出字母内容
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) {
                sgood += tolower(ch);
            }
        }
        // 双指针验证回文串
        int n = sgood.size();
        int left = 0, right = n - 1;
        while (left < right) {
           if (sgood[left] != sgood[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

680 验证回文字符串 Ⅱ (opens new window)

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

输入一个字符串，输出一个布尔值表示该字符串是否能通过删除操作构成回文串

输入: s = "abca"
输出: true
解释: 你可以删除c字符。

解析：

​ 本题采用双指针的方法检验回文串，两个指针分别指向字符串的头和尾，逐一比较两个指针指向的元素。当出现两个指针指向的字符不想等的情况时分别检验将头指针指向的元素删除和将尾指针指向的元素删除两种情况下继续比较字符，是否仍然可以构成回文串。

class Solution {
public:
    bool subPalindrome(string s, int head, int tail){
        for(;head<tail;++head,--tail){
            if(s[head]!=s[tail]){
                return false;
            }
        }
        return true;
    }

    bool validPalindrome(string s) {
        int head = 0, tail = s.size()-1;
        while(head<tail){
            if(s[head]==s[tail]){
                ++head;
                --tail;
            }else{
                if( subPalindrome(s,head,tail-1)||subPalindrome(s,head+1,tail)){
                    return true;
                }else{
                    return false;
                }
            }
        }
        return true;
    }
};

647 回文子串 (opens new window)

给定一个字符串，求其有多少个回文子字符串。回文的定义是左右对称。

输入是一个字符串，输出一个整数，表示回文子字符串的数量。

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解析：

​ 本题采用中心扩展法，可以从字符串的每个位置开始，向左向右延长，判断存在多少以当前位置为中轴的回文子字符串。中心扩展法：枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。枚举过程中要区分子串的长度为偶数情况和奇数情况。

class Solution {
public:
    int countCurSub(string s, int lsh, int rsh){
        int count = 0;
        while(lsh>=0 && rsh<s.length() && s[lsh]==s[rsh]){
            --lsh;
            ++rsh;
            ++count;
        }
        return count;
    }

    int countSubstrings(string s) {
        int ans = 0;
        for(int i=0;i<s.length();++i){
            // 长度为奇数的回文子串
            ans += countCurSub(s,i,i);
            // 长度为偶数的回文子串
            ans += countCurSub(s,i,i+1);
        }
        return ans;
    }
};

409 最长回文串 (opens new window)

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

输入一个字符串，输出一个整数表示可组成的最长回文串长度

输入: "abccccdd"
输出: 7
解释: 可以构造的最长的回文串是"dccaccd", 它的长度是 7。

解析：

​ 本题采用哈希表辅助统计给出字符串中每个字符频次，频次为偶数的可以全部加入构成回文串，频次为奇数的减去一个剩下的也可以加入构成回文串。需要注意的是如果有奇数频次的字符，那么构成的回文串总长可以为奇数，该字符可以出现在回文串中心。

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> chCnt;
        for(const auto ch: s){
            ++chCnt[ch];
        }
        bool hasOdd = false;
        int ans = 0;
        for(const auto [key,cnt]: chCnt){
            if(cnt&1){
                ans+=(cnt-1);
                hasOdd = true;
            }else{
                ans+=cnt;
            }
        }
        return hasOdd?ans+1:ans;
    }
};

5 最长回文子串 (opens new window)

给定一个字符串 s，找到 s 中最长的回文子串。

输入一个字符串，输出一个字符串表示最长回文子串

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

解析：

​ 本题和647 回文子串 (opens new window)相似，可以采用中心扩展法寻找最长回文子串。分别考虑子串长度为奇数和偶数的情况，奇数的中心只有一个，偶数长度的中心为 i 和 i+1；以此中心使用两个指针分别向左向右扩展，逐一比较两个指针指向元素的值是否相等；出现不等情况时，使用一个pair对象返回已经检验的回文子串的起始位置和结束位置。

​ 遍历所有回文子串，比较子串的长度，不断更新较长回文子串的起始和结束位置，最终使用substr()方法切片获得最长回文子串。

class Solution {
public:
    pair<int,int> subStr(string s, int lsh, int rsh){
        while(lsh>=0 && rsh<s.length() &&s[lsh]==s[rsh]){
            --lsh;
            ++rsh;
        }
        return {lsh+1,rsh-1};
    }

    string longestPalindrome(string s) {
        int start = 0, end=0;
        for(int i=0; i<s.length();++i){
            pair<int,int> oddStr = subStr(s,i,i);
            pair<int,int> evenStr = subStr(s,i,i+1);
            if(oddStr.second-oddStr.first > end-start){
                start = oddStr.first;
                end = oddStr.second;
            }
            if(evenStr.second-evenStr.first > end-start){
                start = evenStr.first;
                end = evenStr.second;
            }
        }
        return s.substr(start,end-start+1);
    }
};