# Valid Palindrome

## Question

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

Notice

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.

Example

`"A man, a plan, a canal: Panama"` is a palindrome.

`"race a car"` is not a palindrome.

Challenge

O(n) time without extra memory.

Tags

String Two Pointers Facebook Zenefits Uber

Related Problems

Medium Palindrome Linked List Medium Longest Palindromic Substring

## Analysis

Test Cases需要考虑周到，比如：

`" "` `"a..."` `"...a"` `"a.a"`

## Solution

``````public class Solution {
/**
* @param s A string
* @return Whether the string is a valid palindrome
*/
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}
int i = 0;
int j = s.length() - 1;

while (i < j) {
while (i < s.length() && !isAlphanumeric(s.charAt(i))) {
i++;
}
if (i == s.length()) {
return true;
}
while (j >= 0 && !isAlphanumeric(s.charAt(j))) {
j--;
}

if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
break;
} else {
i++;
j--;
}
}
return (j <= i);
}

public boolean isAlphanumeric(char ch) {
// return Character.isLetter(ch) || Character.isDigit(ch);
boolean result = (ch <= 'z' && ch >= 'a') ||
(ch <= 'Z' && ch >= 'A') ||
(ch <= '9' && ch >= '0');
return result;

}
}``````

Another implementation of isAlphanumeric()

``````    // Use Character methods isLetter(), isDigit()
private boolean isAlphanumeric (char c) {
return Character.isLetter(c) || Character.isDigit(c);
}``````

A verbose way - filter alphanumeric first, then start expanding from middle point of the new string

Time - O(n), Space O(n)

``````class Solution {
public boolean isPalindrome(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isLetter(ch)) {
sb.append(Character.toLowerCase(ch));
} else if (Character.isDigit(ch)) {
sb.append(ch);
}
}

String t = sb.toString();
System.out.println(t);

int i, j;

if (t.length() % 2 == 0) {
// even number
i = (t.length() - 1) / 2;
j = i + 1;

} else {
// odd number
i = t.length() / 2;
j = i;
}
while (i >= 0 && j < t.length()) {
if (t.charAt(i) != t.charAt(j)) {
return false;
}
i--;
j++;
}

return true;
}
}``````

*(Preferred) A concise, one pass (4ms, 92.32%)

``````class Solution {
public boolean isPalindrome(String s) {
int l = 0;
int r = s.length() - 1;
while (l < r) {
char lChar = s.charAt(l);
char rChar = s.charAt(r);
if (!Character.isLetterOrDigit(lChar)) {
l++;
} else if (!Character.isLetterOrDigit(rChar)) {
r--;
} else {
if (Character.toLowerCase(lChar) != Character.toLowerCase(rChar)) {
return false;
}
l++;
r--;
}
}
return true;

}
}``````

## Reference

http://www.jiuzhang.com/solutions/valid-palindrome/

Last updated