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.
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.
Analysis:
1. What is a palindrome?
According to wiki, a palindrome is "A word, phrase, number, or other sequences of symbols or elements that reads the same forward or reversed, with general allowance for adjustments to punctuation and word dividers. "
2. What is the allowance for adjustments to punctuation in this question?
We only need to consider the alphanumeric characters, thus ignoring space, comma, colon, etc. Note that we also ignore cases in this question. So A equals to a.
3. Come up one or two examples to show the problem?
First, is an empty string a palindrome? Yes, at least for this question.
Second, is a string with only one character a palindrome? Yes, since it reads the same with forward and backward.
Third, the example showing above is a palindrome.
Naive Solution:
How to determine if a given string is a palindrome? Remember the definition of the palindrome. A string reads the same forward and backward is a palindrome. Consequently, a brute force solution is to read the string backward from the end, store it into a temp string, and then compare each character of the original string and the temp string. It should be the same if the original string is a palindrome. How complex of this solution is? We need to read the string twice, one to reverse the string, one to compare with the original string. So the total cost is O(n) + O(n) = O(n). Since it needs an additional string to store the reversed string, the space complexity is O(n) as well. Do we have a better solution? The answer is yes.
A Better Solution:
Remember the definition of the palindrome: a string should be read the same forward and backward. As a result, every single character should be the same if we read from start and end. Now you may get the idea. We maintain two pointers, one iterate from start of the string, one from end of the string and iterate the string in a reversed order. We move the two pointers at the same time until we have checked all characters in the string. How abut the complexity of this solution? Since we only iterate the string at most once, the worst case complexity is O(n). In this solution, we don't need to allocate temp buffers to store the reversed string, so it is in-place check and the space complexity is O(1).
For the Java implementation, how to get a char at a given index, we use charAt(int index) instant method. Note that we only consider alphanumeric characters and ignore cases.
First of all, how to check if character is alphanumeric? To check if a character is alphabet or number, we use instance method of Class Character
static boolean isLetter(char ch)
static boolean isDigit(char ch)
Note that they are static methods, so calling the method should be like:
Character.isLetter(ch)
else it is impossible for the compiler to know the instance method isLetter() belongs to which Class.
To handle the lower case and upper case issue, use two instance methods from the Character class
static boolean isLowerCase(char ch)
static boolean isUpperCase(char ch)
Use these two instance methods to convert any upper case characters into lower case. Also note that they are also static methods, so calling the method should be:
Character.isLowerCase(ch);
Code (Java):
public class Solution {
public boolean isPalindrome(String s) {
int length = s.length();
if (length == 0 || length == 1) return true;
int start = 0;
int end = length - 1;
while (start < end) {
// determine if the char is an alphanumeric
while ((start < end) && (!isAlphaNum(s.charAt(start)))) start++;
while ((start < end) && (!isAlphaNum(s.charAt(end)))) end--;
// check if lower case
Character lStart = s.charAt(start);
Character lEnd = s.charAt(end);
if (!Character.isLowerCase(lStart)) lStart = Character.toLowerCase(lStart);
if (!Character.isLowerCase(lEnd)) lEnd = Character.toLowerCase(lEnd);
if (lStart.equals(lEnd)) {
start++;
end--;
} else {
return false;
}
}
return true;
}
private boolean isAlphaNum(char ch) {
return (Character.isLetter(ch) || Character.isDigit(ch)) ? true : false;
}
}
Discussion:
If using the instance methods such as isLetter(char) or isDigit(char) is not allowed, we can simply implement it manually. For example, isLetter(char ch) can be implemented as:
private boolean isLetter(char ch) {
if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
return true;
else
return false;
}
Another Interesting Solution:
I found there is another very interesting solution posted here:
In this solution, we first removed the non-alphanumeric characters from the array and convert all characters to lower cases. After that, we get a very neat string with only lower case characters. Then we employ a stack, and push the first half of the string into the stack, then pop and compare with the second half of the string. The code is as below:
Code (Java):
public class Solution {
public boolean isPalindrome(String s) {
int length = s.length();
if (length < 2) return true;
// Replace the non-alphanumeric characters first
String delim = "[^a-zA-Z0-9]";
s = s.replaceAll(delim, "").toLowerCase();
length = s.length();
if (length < 2) return true;
Stack<character> stack = new Stack<character>();
int index;
for (index = 0; index < length/2; index++) {
stack.push(s.charAt(index));
}
// Handle if the length of string is odd
if (length % 2 == 1) index++;
while (index < length) {
char temp = stack.pop();
if (temp != s.charAt(index)) return false;
else index++;
}
return true;
}
}
The implementation is very straight-forward but tricky. The only thing needs to take care is if the length of the trimmed string is odd, we need to jump the "middle" character in the string. The advantage of the implementation is it iterates the string only from forward order. This is an useful property when the input is a singly linked list, where we can only iterate the list from beginning. The disadvantage of this solution is it needs O(n/2) additional space to store the stack elements. In addition, since string is immutable, the replaceAll() method actually allocates a new string which takes additional O(n) space at the worst case.
Summary
In this question, we used two methods to determine if a string is a palindrome: use two pointers or stack. Last but not least, we can clearly see that for writing neat and efficient Java programs, it is important to be familiar with commonly used Java instance methods. So please memorize as many as you can.
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 start = 0;
int end = s.length() - 1;
while (start < end) {
while (start < end && !Character.isLetterOrDigit(s.charAt(start))) {
start++;
}
while (start < end && !Character.isLetterOrDigit(s.charAt(end))) {
end--;
}
char startChar = Character.toLowerCase(s.charAt(start));
char endChar = Character.toLowerCase(s.charAt(end));
if (startChar != endChar) {
return false;
}
start++;
end--;
}
return true;
}
}
No comments:
Post a Comment