验证回文串

分析

这道题最直观的方法就是利用双指针进行前后遍历。我们可以先利用 erase() 配合 remove_if() 以及 isalnum() 移除所有非法字符。然后利用 transform() 将所有字符转换为小写。接着就可以使用双指针进行前后遍历判断是否回文了。

当然，我们还可以直接在原字符串上判断，从而节省额外空间。我们可以利用上文提到的 isalnum() 函数，在遇见非法字符时进行跳过。然后直接利用 tolower() 对字符进行立即转换并判断。

解答

1
class Solution {
2
public:
3
  bool isPalindrome(string s) {
4
    int n = s.size();
5
    auto left = 0, right = n - 1;
6

7
    while (left < right) {
8
      while (left < right && !isalnum(s[left]))
9
        left++;
10
      while (left < right && !isalnum(s[right]))
11
        right--;
12
      if (left < right)
13
        if (tolower(s[left++]) != tolower(s[right--]))
14
          return false;
15
    }
16

17
    return true;
18
  }
19
};