一、問題描述

在字符串處理中，判斷一個(gè)字符串是否為回文串是一個(gè)經(jīng)典問題。

本題有特殊要求：在將所有大寫字符轉(zhuǎn)換為小寫字符、并移除所有非字母數(shù)字字符之后，如果短語正著讀和反著讀都一樣，則認(rèn)為該短語是一個(gè)回文串。字母和數(shù)字都屬于字母數(shù)字字符。

示例

• 輸入: s = "A man, a plan, a canal: Panama"，輸出：true，解釋：處理后得到 "amanaplanacanalpanama" 是回文串。
• 輸入：s = "race a car"，輸出：false，解釋：處理后得到 "raceacar" 不是回文串。
• 輸入：s = " "，輸出：true，解釋：移除非字母數(shù)字字符后，s 是一個(gè)空字符串 ""，空字符串正著反著讀都一樣，所以是回文串。

 原題鏈接 

125. 驗(yàn)證回文串 - 力扣（LeetCode）

二、解法一：將字母數(shù)字連接到新的 string

思路

這種方法的核心思想是先遍歷原字符串，把其中的字母數(shù)字字符提取出來，同時(shí)將大寫字母轉(zhuǎn)換為小寫字母，存儲(chǔ)到一個(gè)新的字符串 tmp 中

然后再對(duì)新字符串 tmp 進(jìn)行回文判斷

代碼實(shí)現(xiàn)

#include <iostream>
#include <string>
 
class Solution {
public:
    bool isPalindrome(string s) //第一種方式 將字母數(shù)字連接到新的string
    {
        string tmp;
        string::iterator left = s.begin();
        string::iterator right = s.end();
 
        while (left != right)//第一次遍歷，所有字母數(shù)字轉(zhuǎn)入新string，并且統(tǒng)一為小寫
        {
            if ((*left >= '0' && *left <= '9') || (*left >= 'a' && *left <= 'z'))
                tmp += *left;
            if (*left >= 'A' && *left <= 'Z')
                tmp += (*left + 32);
            ++left;
        }
 
        if (tmp.empty())//如果新string為空，則判定為回文串
            return true;
 
        left = tmp.begin();
        right = tmp.end() - 1;
        while (left <= right)//第二次遍歷 左右迭代器逐個(gè)對(duì)比
        {
            if (*left == *right)
            {
                ++left;
                --right;
            }
            else
                return false;
        }
        return true;
    }
};

代碼解釋

1. 提取字母數(shù)字并轉(zhuǎn)換大小寫：
   • 定義一個(gè)空字符串 tmp 用于存儲(chǔ)處理后的字符。
   • 使用迭代器 left 遍歷原字符串 s，當(dāng)遇到數(shù)字（'0' 到 '9'）或小寫字母（'a' 到 'z'）時(shí)，直接添加到 tmp 中；當(dāng)遇到大寫字母（'A' 到 'Z'）時(shí)，將其 ASCII 碼值加 32 轉(zhuǎn)換為小寫字母后添加到 tmp 中。
2. 處理空字符串情況：如果 tmp 為空字符串，根據(jù)題目定義，空字符串是回文串，直接返回 true。
3. 回文判斷：使用雙指針法，left 指向 tmp 的開頭，right 指向 tmp 的結(jié)尾，逐個(gè)比較對(duì)應(yīng)位置的字符。如果不相等，返回 false；如果都相等，最終返回 true。

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O（n）需要遍歷原字符串一次，再遍歷新字符串一次。
• 空間復(fù)雜度：O (n)，其中  n是處理后新字符串的長度。

三、解法二：直接原地篩選判斷

思路

這種方法不創(chuàng)建新的字符串，而是直接在原字符串上使用雙指針法進(jìn)行篩選和判斷。通過兩個(gè)指針 left 和 right 分別從字符串的兩端開始向中間移動(dòng)，跳過非字母數(shù)字字符，同時(shí)將字符轉(zhuǎn)換為小寫后進(jìn)行比較。

代碼實(shí)現(xiàn)

#include <iostream>
#include <string>
#include <cctype>
 
class Solution {
public:
    bool isPalindrome(std::string s) //第二種方式，直接原地篩選判斷
    {
        string::iterator left = s.begin();
        string::iterator right = s.end() - 1;
 
        while (left < right)
        {
            // 跳過左邊的非字母數(shù)字字符
            while (left < right && !isalnum(*left))
            {
                ++left;
            }
            // 跳過右邊的非字母數(shù)字字符
            while (left < right && !isalnum(*right))
            {
                --right;
            }
 
            if (left < right) {
                // 將字符轉(zhuǎn)換為小寫后比較
                if (tolower(*left) != tolower(*right))
                {
                    return false;
                }
                ++left;
                --right;
            }
        }
        //跳出循環(huán)，要么left==right,要么left>right 
        //說明所有需要比較的字符對(duì)都已經(jīng)檢查過，且都相等
        return true;
    }
};

代碼解釋

1. 初始化指針：使用迭代器 left 指向字符串的開頭，right 指向字符串的結(jié)尾。
2. 跳過非字母數(shù)字字符：通過兩個(gè)內(nèi)層 while 循環(huán)，分別將 left 和 right 指針移動(dòng)到字母數(shù)字字符的位置。
3. 字符比較：將 left 和 right 指針指向的字符轉(zhuǎn)換為小寫后進(jìn)行比較，如果不相等，返回 false；如果相等，繼續(xù)移動(dòng)指針。
4. 返回結(jié)果：當(dāng) left 大于等于 right 時(shí)，說明所有需要比較的字符對(duì)都已經(jīng)檢查過，且都相等，返回 true。

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O（n），只需要遍歷一次字符串。
• 空間復(fù)雜度：O（1），只使用了常數(shù)級(jí)的額外空間。

總結(jié)

兩種解法都能有效解決回文串判斷問題:

解法一邏輯清晰，易于理解，但需要額外的空間存儲(chǔ)處理后的字符串；

解法二原地操作，空間復(fù)雜度更低，更適合處理大規(guī)模數(shù)據(jù)。在實(shí)際應(yīng)用中，可以根據(jù)具體需求選擇合適的解法。

以上就是C++實(shí)現(xiàn)回文串判斷的兩種高效方法的詳細(xì)內(nèi)容，更多關(guān)于C++回文串判斷的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論