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.
Naive Way: Keep two pointers starting from both beginning and end, check equality of two valid characters.
public class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
int begin = 0, end = s.length()-1;
while(begin < end){
while(!isAlphanumeric(s.charAt(begin)) && begin < end) begin++;
while(!isAlphanumeric(s.charAt(end)) && begin < end) end--;
if(s.charAt(begin)!= s.charAt(end)) return false;
begin++;
end--;
}
return true;
}
public boolean isAlphanumeric(char c){
return c >= '0' && c <='9' || c >= 'a' && c <= 'z';
}
}
No comments:
Post a Comment