125 Valid Palindrome

1. Question

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"isnota 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.

2. Implementation

(1) Two Pointers
1
class Solution {
2
public boolean isPalindrome(String s) {
3
if (s == null || s.length() == 0) {
4
return true;
5
}
6
7
int start = 0, end = s.length() - 1;
8
9
while (start < end) {
10
if (!Character.isLetterOrDigit(s.charAt(start))) {
11
++start;
12
}
13
else if (!Character.isLetterOrDigit(s.charAt(end))) {
14
--end;
15
}
16
else if (Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))) {
17
return false;
18
}
19
else {
20
++start;
21
--end;
22
}
23
}
24
return true;
25
}
26
}
Copied!

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)