【Leetcode】【Easy】Valid Palindrome

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

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

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

解题思路：

建立两个index，同时从前从后遍历字符串。遇到非字符需要跳过，遇到大写字母将其转为小写字母。比较两个index指向的字母，如果一致则继续遍历下一组，如果不相同则返回false，最后返回true；

注意：

1、非字母不需要比较，要跳过；

2、注意统一大小写；

 1 class Solution {
 2 public:
 3     bool isPalindrome(string s) {
 4         int len = s.length();
 5         int front = 0;
 6         int behind = len - 1;
 7         
 8         if (!len) 
 9             return true;
10             
11         while (front <= behind) {
12             
13             if (!isAlphanumeric(&s[front])) {
14                 front++;
15                 continue;
16             }
17             
18             if (!isAlphanumeric(&s[behind])) {
19                 behind--;
20                 continue;
21             }
22 
23             if (s[front] != s[behind]) {
24                 return false;
25             } else {
26                 front ++;
27                 behind --;
28             }
29                 
30         }
31         
32         return true;
33     }
34     
35     bool isAlphanumeric(char *s) {
36         if ((*s>='a' && *s<='z') || (*s>='0' && *s<='9'))
37             return true;
38         if (*s>='A' && *s<='Z') {
39             *s += 32;
40             return true;
41         }
42         return false;
43     }
44     
45 };

另，有些程序直接使用了C++中isalnum()和tolower()函数，思路是一样的：

 1 class Solution {
 2 public:
 3     bool isPalindrome(string s) {
 4         int len = s.length();
 5         int front = 0;
 6         int behind = len - 1;
 7         
 8         if (!len) 
 9             return true;
10             
11         while (front <= behind) {
12             if (!isalnum(s[front])) {
13                 front++;
14                 continue;
15             }
16             
17             if (!isalnum(s[behind])) {
18                 behind--;
19                 continue;
20             }
21 
22             if (tolower(s[front]) != tolower(s[behind])) {
23                 return false;
24             } else {
25                 front ++;
26                 behind --;
27             }
28         }
29         
30         return true;
31     }
32 };

附录：

常用字符ASCII值