Valid Palindrome

Once during a technical interview, I was asked to validate whether a sentence is a palindrome or not. But what’s a palindrome? A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as "A man, a plan, a canal, Panama!", "Was it a car or a cat I saw?" or "No 'x' in Nixon".

My Solution

During the interview I just reverse the sentence and compare with the original sentence. Even ignore case and punctuation it’s still wrong. How could “Was I tac a ro rac a ti saw?” be the same with "Was it a car or a cat I saw?”. Obviously the problem is space. What if I even ignore space?

"Talk is cheap. Show me the code."

public boolean isPalindrone(String s) {
    String pattern = "\\w";
    Pattern r = Pattern.compile(pattern);
    Matcher m = r.matcher(s);

    StringBuilder sb = new StringBuilder();

    while(m.find()) {
        sb.append(m.group(0));
    }

    String oldString = sb.toString();
    String reversedString = sb.reverse().toString();

    if (!oldString.equalsIgnoreCase(reversedString)) {
        return false;
    }

    return true;
}

Another Solution

You can also find the problem on LeetCode. I find a more elegant sultion there. Here is the codes.

public boolean isPalindrome(String s) {
    if (s.isEmpty()) {
        return true;
    }
    int head = 0, tail = s.length() - 1;
    char cHead, cTail;
    while(head <= tail) {
        cHead = s.charAt(head);
        cTail = s.charAt(tail);
        if (!Character.isLetterOrDigit(cHead)) {
            head++;
        } else if(!Character.isLetterOrDigit(cTail)) {
            tail--;
        } else {
            if (Character.toLowerCase(cHead) != Character.toLowerCase(cTail)) {
                return false;
            }
            head++;
            tail--;
        }
    }
    return true;
}

All point here is that the first letter or digit character must be the same with the last letter or digit character and the second must be the same with the reciprocal second and so on.

Conclusion

The two solutions represent two totally different ways of thinking the problem. My solution is from Macro and the other one is from Micro. In my opinion solving this kind of problem from Micro is more difficult and thus more elegant.

BTW you can find a lot of Palindromic Sentences from here and you can do some test.