一、題目描述與要求

125. 驗證回文串 - 力扣（LeetCode）

題目描述

如果在將所有大寫字符轉(zhuǎn)換為小寫字符、并移除所有非字母數(shù)字字符之后，短語正著讀和反著讀都一樣。則可以認為該短語是一個?回文串 。

字母和數(shù)字都屬于字母數(shù)字字符。

給你一個字符串 s，如果它是 回文串 ，返回 true ；否則，返回 false 。

示例

示例1：

輸入: s = "A man, a plan, a canal: Panama"
輸出：true
解釋："amanaplanacanalpanama" 是回文串。

示例2：

輸入：s = "race a car"
輸出：false
解釋："raceacar" 不是回文串。

?示例3：

輸入：s = " "
輸出：true
解釋：在移除非字母數(shù)字字符之后，s 是一個空字符串 "" 。
由于空字符串正著反著讀都一樣，所以是回文串。

提示

• 1 <= s.length <= 2 * 105
• s?僅由可打印的 ASCII 字符組成

二、解題思路

總的思路：

? ? ? ?首先根據(jù)題目要求可以有兩種大的解題方法：一是對數(shù)組本身進行修改，將其改成要進行判斷的形式然后判斷其是否為回文串；二是利用雙指針的方式，對于要排除的字符選擇跳過，以此來判斷整個字符串是否為回文串?！鞠旅嫣岬降南聵俗兞恐傅氖怯脕碇甘鞠聵说恼妥兞俊?/p>

? ? ? ?對于第一種方法，則需要我們首先將數(shù)組中的所有大寫字符都轉(zhuǎn)成小寫字符，其實也就是26個字母的大寫轉(zhuǎn)成小寫，利用“ch=ch+32”即可實現(xiàn)。然后就是將數(shù)組中所有非字母數(shù)字字符進行移除，也就是刪去除字母和數(shù)字以外的其他字符，可以利用覆蓋的思想，在每次找到非字母數(shù)字字符時將后面所有字符往前覆蓋，覆蓋只需要利用到一個下標變量（時間較長）。也可以使用兩個下標變量，一個用來遍歷整個數(shù)組，另一個用來記錄修改后的數(shù)組。然后就是直接對修改后的數(shù)組首尾字符進行比較來判斷其是否為回文串。

? ? ? ?對于第二種方法，則需要我們設(shè)置一個判定條件，即只有當兩個字符都是字母或者數(shù)字才對其進行比較，一旦有一方不是，則需要尋找下一個字符用來比較，也就是所謂的“跳過”。這一方法需要利用到“雙指針”，也就是兩個下標變量。兩方都是的情況下則只需要修改大寫字母為小寫，然后進行判斷是否相同，相同則移動指針繼續(xù)比較直至遍歷結(jié)束/發(fā)現(xiàn)不是回文串則結(jié)束。【在實現(xiàn)這一方法的過程中，就是判斷字符是否是字母/數(shù)字字符的代碼比較長，看起來很亂，因而可以選擇將其單獨寫成一個函數(shù)】【修改大寫字母為小寫可以在判斷字符前把整個數(shù)組都進行修改，也可以在判斷后在對其進行修改】

具體步驟：

方法一：

①遍歷數(shù)組，將大寫字符全部轉(zhuǎn)換成小寫字符

②將數(shù)組中所有非字母數(shù)字字符進行移除【可以分為利用幾個下標變量】

③獲取數(shù)組長度

④判斷修改后的字符串是否為回文串

方法二：

①獲取數(shù)組長度

②將數(shù)組中的所有大寫字符轉(zhuǎn)成小寫字符

③判斷首尾字符是否為字母數(shù)字字符，并判斷是否相等，然后移動指針，直至獲得結(jié)果文章來源地址http://www.zghlxwxcb.cn/news/detail-521147.html

三、具體代碼【C語言】

①只采用一個下標變量來對數(shù)組進行修改（覆蓋）【超時，但步驟清晰，可用于理解】

bool isPalindrome(char* s) {
    int i = 0, j = 0;
    for (int i = 0; s[i] != '\0'; i++) { //遍歷數(shù)組，將大寫字符全部轉(zhuǎn)換成小寫字符
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] += 32;
        }

    }
    while (s[i] != '\0') {
        if ((s[i] >= '0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z')) //是數(shù)字或者字母字符 訪問下一個
        {
            i++;
        }
        else { //不是數(shù)字或者字符 覆蓋并繼續(xù)檢查
            for (j = i; s[j] != '\0'; j++) {
                s[j] = s[j + 1];
            }
            s[j - 1] = '\0';//此時j-1指向最后一個字符的后面第一位
        }
    }
    int len = strlen(s);
    //k=j-2是因為，數(shù)組下標從0開始，j-1是結(jié)束符的下標，j-2就是最后一個字符的下標
    for (int i = 0, k = len - 1; i < k; i++) {
        if (s[i] != s[k])
            return false;
        else k--;
    }
    return true;
}

②對①進行修改，即利用兩個下標變量來實現(xiàn)數(shù)組的修改【大寫改小寫與覆蓋同時進行】【最快】

bool isPalindrome(char* s) {
    int i = 0, j = 0;
    for (int i = 0; s[i] != '\0'; i++) { //遍歷數(shù)組，將大寫字符全部轉(zhuǎn)換成小寫字符
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[j++] = s[i] + 32;
        }
        else if ((s[i] >= '0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z')) {
            s[j++] = s[i];
        }
    }
    //此時j指向調(diào)整后的數(shù)組的結(jié)束符
    for (int i = 0, k = j - 1; i < k; i++) {
        if (s[i] != s[k])
            return false;
        else k--;
    }
    return true;
}

③不對數(shù)組進行修改，直接進行比較

bool Judge(char ch) {
    if ( (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')) {
        return true;
    }
    else {
        return false;
    }
}

bool isPalindrome(char * s){
    int j=strlen(s)-1;
    for(int i=0;s[i]!='\0';i++){ //遍歷數(shù)組，將大寫字符全部轉(zhuǎn)換成小寫字符
        if (s[i] >= 'A' && s[i] <= 'Z')  s[i]+=32;
    }
    for (int i = 0; s[i]!='\0'; i++) { 
        while(i<j){
            if(Judge(s[i])&&Judge(s[j])){
               if(s[i]!=s[j])  return false;
               i++; j--;
            }
            else if(!Judge(s[i])){
            i++;
            }
            else{
            j--;
            }
        }
    }
    return true;
}

?

到了這里，關(guān)于2023年7月2日leetcode每日一題打卡——125.驗證回文串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！