LeetCode Valid Palindrome: O(N) Time and O(1) Space with Two Pointers

Overview

LeetCode Valid Palindrome: It could be solved in O(N) Time and O(1) Space with Two Pointers to scan the characters from both end and compare the characters.

LeetCode Valid Palindrome

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.

For the purpose of this problem, we define empty string as valid palindrome.

Solution: O(N) Time and O(1) Space with Two Pointers

This problem is an easy one, but a little bit change from the regular palindrome problem, the algorithm is straightforward just scan through the string using head and tail pointer until these two pointer hit each other, and by definition, determine if the character pointed at head and tail is the same as each other(ignoring  cases and ignoring those non-alphanumeric characters). If all are the “same”, then it is, otherwise it is not valid. And don’t forget to check the boundary of the pointers, otherwise, there would be run time error (usually segment fault). The following code is accepted by LeetCode OJ to apss this Valid Palindrome problem and for simplicity I actually use extra O(N) space to keep the lower case version of the input:

class Solution {
    public boolean isPalindrome(String s) {
        String sLowerCase = s.toLowerCase();
        int i = 0,
            j = s.length() - 1;

        while (i <= j) {
            if (!Character.isLetterOrDigit(
                    sLowerCase.charAt(i)))
                ++i;

            if (!Character.isLetterOrDigit(
                    sLowerCase.charAt(j)))
                --j;

            if (i <= j &&
                Character.isLetterOrDigit(
                              sLowerCase.charAt(i))
                       &&
                Character.isLetterOrDigit(
                              sLowerCase.charAt(j))) {

                if (sLowerCase.charAt(i) !=
                    sLowerCase.charAt(j))
                    return false;
                else {
                   ++i;
                   --j;
                }
            }
        }
        return true;
    }
}

And the following two implementation slightly differs from the above, just for your further reference.

public class ValidPalindrome {

	public boolean isPalindrome(String s) {
		if (Math.random() < 0.5) {
			return isPalindrome1(s);
		} else {
			return isPalindrome2(s);
		}

	}

	public boolean isPalindrome1(String s) {

		int i = 0,
		    j = s.length() - 1;

		while (i < j) {
			while (i < j &&
                              !Character.isLetterOrDigit(s.charAt(i))) {
  			    ++i;
			}

			while (i < j &&
                              !Character.isLetterOrDigit(s.charAt(j))) {
			    --j;
			}

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

		return true;
	}

	private boolean isPalindrome2(String s) {

		String lowerCases = s.toLowerCase();
		int i = 0,
                    j = s.length() - 1;

		while (i < j) {
			char a = lowerCases.charAt(i);
			if (!Character.isLetterOrDigit(a)) {
				++i; continue;
			}

			char b = lowerCases.charAt(j);
			if (!Character.isLetterOrDigit(b)) {
				--j; continue;
			}

			if (a != b) {
				return false;
			}
			++i;
			--j;
		}
		return true;
	}
}

Also take a look at this similar problem but applies to Linked List: LeetCode Palindrome Linked List: O(1) Space 

Summary

LeetCode Valid Palindrome: It could be solved in O(N) Time and O(1) Space with Two Pointers to scan the characters from both end and compare the characters.

Written on January 26, 2013