自贡市网站建设市场营销策划ppt

1. 125 验证回文串 简单

1. 题目详情

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

1. 原题链接

LeetCode 125 验证回文串 简单

2. 题目要求

示例 1：
输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。

示例 2：
输入：s = “race a car”
输出：false
解释：“raceacar” 不是回文串。

示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

提示：
1 <= s.length <= 2 * 105
s 仅由可打印的 ASCII 字符组成

3. 基础框架

● Cpp代码框架

class Solution {
public:bool isPalindrome(string s) {}
};

2. 解题思路

1. 思路分析

$(1)$ 快排思想，借助两个变量$l$和$r$
$(2)$ $l$从字符串起始0下标位置向后找到第一个字母字符;
$(3)$ $r$从字符串最后一个字符size-1下标位置开始向前找到第一个字母字符;
$(4)$ 对找到的两个字母字符分别进行判断，如果是大写字母则变为小写字母;
$(5)$ 比较这两个字母字符，相等就$l$和$r$就继续分别查找下一个字母字符，直到$l$和$r$相遇说明所有须比较的字母字符都符合要求，结束并返回true；只有存在一对不相等的字母字符说明不是回文串，直接返回false；

2. 时间复杂度

$O(N)$
$l$向后查找，$r$向前查找，直到二者相遇时才结束查找，共查找了$n$次;

3. 代码实现

class Solution {
public:bool isPalindrome(string s) {int l = 0, r = s.size() - 1;while(l < r){while(l < s.size() && !isalpha(s[l]) && !isdigit(s[l])){l++;}while(r >= 0 && !isalpha(s[r]) && !isdigit(s[r])){r--;}if(l < r){if(isupper(s[l])) s[l] += 32;if(isupper(s[r])) s[r] += 32;if(s[l] != s[r]) return  false;l++;r--;}}return true;}
};

---

$The$ $end$