LeetCode125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

1
2
Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

1
2
Input: "race a car"
Output: false

Two Pointers

my code in cpp

1
2
3
4
5
6
7
8
9
10
bool isPalindrome(string s) {
int l = 0, r = s.size() - 1 ;
while (r<s.size()&&l < r) {//1.
while (l<s.size()&&!isalnum(s[l])) ++l;//2.
while (r<s.size()&&!isalnum(s[r])) --r;
if (l<s.size()&&r<s.size()&&(s[l++] + 32 - 'a') %32 != (s[r--] + 32 - 'a') % 32) return false;//3.

}
return true;
}

细节

  1. 开始写成while (!isalnum(s[l]))报错: heap-buffer-overflow。后来想想一定是数组越界的问题,只需要在每次while和if的时候都判断是否下标超过size()即可。
  2. 有一个内置函数isalnum(char)来表示是否是数字和字母,自己写就这样。
1
2
3
4
5
6
bool isAlphaNum(char &ch) {
if (ch >= 'a' && ch <= 'z') return true;
if (ch >= 'A' && ch <= 'Z') return true;
if (ch >= '0' && ch <= '9') return true;
return false;
}
  1. 如果直接取绝对值,写成 (abs(s[l] -s[r]) !=0&&abs(s[l] -s[r]) !=32) 会报错:”0P”。这里0是48,P是80,相隔32,所以不能用ascii相隔0和32来判断。所以用(char-‘a’+32)%32来将大写转成小写来判断两个字母是否相等,”OP”分别是-17和15,所以这两个不等。
Thanks for Support.