Leetcode 验证回文串
使用双指针技术，逐步比较字符串中的字符，并忽略非字母数字字符以及大小写，判断该字符串是否为回文。以下是详细解释：
1. 核心思想：
- 回文串是指正读和反读都相同的字符串。我们需要从字符串的两端开始比较字符，跳过非字母数字字符，并忽略大小写，直到双指针相遇或者交错。
- 比如字符串
"A man, a plan, a canal: Panama"，当忽略空格、标点符号，且不区分大小写时，实际上是回文。
2. 算法步骤：
2.1 初始化双指针：
int left = 0, right = s.length() - 1;
left指针指向字符串的第一个字符。right指针指向字符串的最后一个字符。
2.2 循环比较：
while (left < right) {
- 这个循环是双指针的核心部分。它会一直执行，直到
left指针和right指针交错或相遇。每次循环中，我们逐步比较左右两边的字符。
2.3 跳过非字母数字字符：
while (left < right && !isalnum(s[left])) {
left++;
}
while (left < right && !isalnum(s[right])) {
right--;
}
isalnum是 C++ 的标准函数，作用是判断字符是否为字母或数字。如果s[left]或s[right]不是字母或数字，我们会将left右移或right左移，直到找到有效字符。
2.4 忽略大小写比较字符：
if (tolower(s[left]) != tolower(s[right])) {
return false;
}
tolower是 C++ 的标准函数，用于将字符转换为小写字母。我们使用它来忽略大小写的影响。- 如果左右指针指向的字符不相等，我们就可以判断字符串不是回文，直接返回
false。
2.5 移动指针：
left++;
right--;
- 如果左右指针的字符相等，我们就继续向内移动
left和right，分别向中间推进，直到它们相遇或者交错。
2.6 循环结束：
- 当
left>=right时，循环结束。如果在此之前没有返回false，说明所有字符匹配，字符串是回文。
2.7 返回结果：
return true;
- 如果所有字符匹配，函数最后返回
true，表示字符串是回文。
3. 算法时间复杂度：
- 该算法的时间复杂度是 O(n)，其中
n是字符串的长度。- 因为我们使用了双指针技术，每次循环中最多移动
left或right，从而保证每个字符最多被访问一次。 - 由于要遍历整个字符串，这导致时间复杂度是线性的。
- 因为我们使用了双指针技术，每次循环中最多移动
4. 示例分析：
示例 1: "A man, a plan, a canal: Panama"
- 忽略大小写和非字母数字字符后，字符串变为
"amanaplanacanalpanama"。 - 正读和反读相同，所以该字符串是回文，函数返回
true。
示例 2: "race a car"
- 忽略大小写和非字母数字字符后，字符串变为
"raceacar"。 - 正读是
"raceacar"，反读是"racacear"，不相同，所以该字符串不是回文，函数返回false。
示例 3: ""（空字符串）
- 空字符串被认为是回文，因为它正读和反读都是空的，因此返回
true。
class Solution {
public:
bool isPalindrome(string s) {
int left = 0;
int right = s.size() - 1;
while(left < right) {
//先分别把左右指针都移动到字母或数字字符上, isalnum会判断是否是字母或数字，不是的话返回false
while(left < right && !isalnum(s[left])) {
left++;
}
while(left < right && !isalnum(s[right])) {
right--;
}
//此时左右指针指向的都是字母或数字字符,然后进行比较
if(tolower(s[left]) != tolower(s[right])) {
return false;
}
//此时说明当前两个字符是相等的，那么分别移动左右指针。
left++;
right--;
}
return true;
}
};
为什么这一部分代码片段中，这两个while循环仍然需要判断left<right?外面的while循环不是已经判断了吗？
// 找到左边第一个字母或数字字符
while (left < right && !isalnum(s[left])) {
left++;
}
// 找到右边第一个字母或数字字符
while (left < right && !isalnum(s[right])) {
right--;
}
```
这是一个非常好的问题！下面解释为什么在这两个 `while` 循环中仍然需要判断 `left < right`，即使外层已经有了 `while (left < right)` 的判断。
### 原因：
在外层的 `while` 循环中，我们逐步推进左右指针来判断字符是否匹配。而在内部的两个 `while` 循环中，我们跳过非字母数字字符（如标点符号、空格等），找到第一个有效的字符来进行比较。然而，由于内部的 `while` 循环是在跳过无效字符的过程中操作的，可能会导致左右指针超越彼此，从而需要再次检查 `left < right` 的条件。
#### 举个例子来说明：
考虑一种特殊情况，假设字符串中有大量非字母数字字符，比如：
```cpp
s = "!!!!!!!"
在这个例子中，字符串的所有字符都不是字母或数字，所以我们希望通过内部的 while 循环将 left 和 right 快速移动，直到超越彼此。但是，如果不加 left < right 的判断，可能会发生如下情况：
left和right都从两端开始，同时跳过无效字符。left可能会超过right。- 此时，如果不再检查
left < right，指针会继续移动，导致程序出现逻辑错误，甚至可能访问到数组的非法区域（即超出字符串范围的索引）。
为了防止这种情况的发生，必须在内部的 while 循环中加上 left < right 的检查，以确保即使在跳过无效字符的过程中，左右指针也不会超越对方。
代码片段解析：
// 找到左边第一个字母或数字字符
while (left < right && !isalnum(s[left])) {
left++;
}
- 这个
while循环是为了从左边跳过所有非字母数字字符，直到找到一个有效的字符。 - 但如果所有字符都是无效字符（如空格、标点符号等），那么
left可能会一直增加，直到超过right。 - 因此，我们在每次移动
left时，都需要再次检查left < right，以确保指针不越界。
同理，对于右边的 while 循环：
// 找到右边第一个字母或数字字符
while (left < right && !isalnum(s[right])) {
right--;
}
- 我们需要右指针
right从右向左移动，跳过所有非字母数字字符。 - 同样，如果没有有效字符存在，
right可能会不断减少，最终低于left。 - 需要确保在跳过字符时，
right不会越过left，因此需要检查left < right。
总结：
尽管外层的 while (left < right) 控制了总体循环，但内部的 while 循环在跳过无效字符时，左右指针可能会过多地移动，因此需要在内部的循环中再次检查 left < right，以防止指针越界或交错的情况发生。这是确保算法正确性和防止潜在错误的关键步骤。
原文地址：https://blog.csdn.net/coldasice342/article/details/142284710
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！