文章目錄

• 一、題目
• • 1、題目描述
  • 2、基礎框架
  • 3、原題鏈接
• 二、解題報告
• • 1、思路分析
  • 2、時間復雜度
  • 3、代碼詳解
• 三、本題小知識

10年積累的成都網(wǎng)站設計、成都網(wǎng)站建設經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先做網(wǎng)站設計后付款的網(wǎng)站建設流程，更有越秀免費網(wǎng)站建設讓你可以放心的選擇與我們合作。一、題目 1、題目描述

如果在將所有大寫字符轉(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 是一個空字符串 “” 。
由于空字符串正著反著讀都一樣，所以是回文串。

2、基礎框架 3、原題鏈接 二、解題報告 1、思路分析

?? ( 1 ) (1) (1)判斷回文串，首先想到雙指針分別從首尾開始，一個往后，一個往前同時遍歷，判斷字符是否相同。
?? ( 2 ) (2) (2)題目中的字符串中還包含了除數(shù)字字母之外的符號，要求無視這些符號，我們可以在指針遍歷到這些符號時直接跳過。
?? ( 3 ) (3) (3)同時題目不考慮大小寫，所以除了判斷字母是否相等外，如果不相等還要判斷是否是對應的大小寫字母。

2、時間復雜度

最壞時間復雜度為O(n),空間復雜度為O(1)

3、代碼詳解

C++

class Solution {public:
    bool isPalindrome(string s) {int l = 0;
        int r = s.length()-1;
        while(lwhile(isTrue(s[l]) == 0 && l< r) {l++;
            }
            while(isTrue(s[r]) == 0 && l< r) {r--;
            }
            if (isTrue(s[l]) != isTrue(s[r])) return false;
            l++;
            r--;
        }
        return true;
    }

    int isTrue (char c) {if (c >= '0' && c<= '9'){return 1 + (c-'0');
        }
        if (c >= 'a' && c<= 'z'){return 11 + (c - 'a');
        }
        if (c >= 'A' && c<= 'Z'){return 11 + (c - 'A');
        }
        return 0;
    }
};

三、本題小知識

1.對撞指針的應用

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：(雙指針之對撞指針)leetcode125.驗證回文串-創(chuàng)新互聯(lián)
文章地址：http://chinadenli.net/article28/edgjp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供電子商務、網(wǎng)站維護、全網(wǎng)營銷推廣、云服務器、營銷型網(wǎng)站建設、關鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)