LCR018-LCR020回文字符串

剑指offer（专项突破版）3.3 回文字符串

LCR018.验证回文串

分析

使用双指针，起始时左指针指向开始，右指针指向最后一个字符，左指针不断后移，右指针不断前移。注意边界条件的判断。

class Solution {
public:
    // 判断是否是字母或数字，数字返回1，大写字母返回2，小写字母返回3，其他返回0
    int checkChar(char &c){
        if(c>=48&&c<=57){
            return 1;
        }
        else if(c>=65&&c<=90){
            c += 32;    // 转换成小写字母
            return 2;
        }
        else if(c>=97&&c<=122){
            return 3;
        }
        else{
            return 0;
        }
    }
    bool isPalindrome(string s) {
        // 双指针分别指向第一个和最后一个字符
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){
            int typeI = checkChar(s[i]);
            int typeJ = checkChar(s[j]);
            while(i <= j && typeI == 0){    // 不是数字或字母，跳过
                i++;
                typeI = checkChar(s[i]);
            }
            while(i <= j && typeJ == 0){    // 不是数字或字母，跳过
                j--;
                typeJ = checkChar(s[j]);
            }
            if(i<=j && s[i]==s[j]){         // i、j所指字符相等，继续移动指针
                i++;
                j--;
            }
            else if(i>j){                   // i已经移动到j的右边，则要么是跳过了，要么是都相等
                return true;
            }
            else                            // i<=j且所指字符不相等，直接返回false
                return false;
        }
        return true;
    }
};

复杂度分析

主要的时间消耗在于 while 循环中的字符比较和移动指针操作。假设字符串的长度为 n，则最坏情况下，每个字符都要被比较一次，而且指针移动的次数也是线性的。因此，while 循环的时间复杂度是 O(n)。
整体上，算法的时间复杂度为 O(n)。

LCR019.验证回文串II

分析

其实跟第一道题有点像，这道题虽然说可以最多去掉一个字符，但是这道题的字符串只由小写字母组成，可以把不匹配的第一个字符当作上一题中的特殊字符跳过，并且这道题只能跳过一次。

代码

一种错误的解法：去掉s[i]还是s[j]，是不知道的，不能按照如下代码的方式判断。

class Solution {
public:
    bool validPalindrome(string s) {
        // 双指针解法
        // i指向第一个字符，j指向最后一个字符
        int i = 0;
        int j = s.length() - 1;
        bool flag = false;  // 没有去掉过字符
        while(i <= j){
            if(s[i] == s[j]){
                i++;
                j--;
            }
            else if(!flag && i+1 <= j && s[i+1] == s[j]){
                i += 2;
                j--;
                flag = true;
            }
            else if(!flag && i <= j-1 && s[i] == s[j-1]){
                i++;
                j -= 2;
                flag = true;
            }
            else{
                return false;
            }
        }
        return true;
    }
};

更正代码：

class Solution {
public:
bool checkPalindrome(string s, int low, int high){
    for(int i = low,j = high;i < j; i++, j--){
        if(s[i] != s[j]){
            return false;
        }
    }
    return true;
}

    bool validPalindrome(string s) {
        // 双指针解法
        // low指向第一个字符，high指向最后一个字符
        int low = 0;
        int high = s.length() - 1;
        bool flag = false;  // 没有去掉过字符
        while(low < high){
            if(s[low] == s[high]){
                low++;
                high--;
            }
            else{
                return checkPalindrome(s, low, high-1) || checkPalindrome(s, low+1,high);
            }
        }
        return true;
    }
};

复杂度分析

时间复杂度：O(n)，其中n是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是O(n)，遇到不同字符时，判断两个子串是否是回文字符串的时间复杂度也都是O(n)。

空间复杂度：O(1)。只需要维护有限的常量空间。

LCR020.回文子串

分析

对每个字符串的每个字符，都作为回文串中心向两侧扩展，回文串长度若为奇数，则只有一个中心；若为偶数，则有两个中心。

代码

class Solution {
public:
    // 比较是否是回文串并计数
    int countPalindrome(string s, int start, int end){
        int count = 0;
        while(start >= 0 && end < s.length() && s[start] == s[end]){
            count++;
            start--;
            end++;
        }
        return count;
    }
    int countSubstrings(string s) {
        int count = 0;
        // 每个字符都作为回文串中心
        int n = s.length();
        for(int i = 0; i < n; i++){
            count += countPalindrome(s, i, i);
            count += countPalindrome(s, i, i+1);
        }
        return count;
    }
};

复杂度分析

时间复杂度是$O（n^2）$，空间复杂度是$O（1）$。

总结

变位词和回文是很有意思的文字游戏，在与字符串相关的算法面试题中，它们出现的频率很高。如果两个字符串包含的字符及每个字符出现的次数都相同，只是字符出现的顺序不同，那么它们就是一组变位词。通常可以用一个哈希表来统计每个字符出现的次数，有了哈希表就很容易判断两个字符串是不是一组变位词。

回文是一类特殊的字符串。不管是从前往后还是从后往前读取其每一个字符，得到的内容都是一样的。通常可以用两个指针来判断一个字符串是不是回文，要么两个指针从字符串的两端开始向中间移动，要么两个指针从中间开始向两端移动。