[LeetCode] Problem 125 - Valid Palindrome

Posted on | In ,

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

Note

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

Example

No.1

Input: “A man, a plan, a canal: Panama”

Output: true

No.2

Input: “race a car”

Output: false

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// O(n) runtime, O(1) space
public boolean isPalindrome(String s) {
    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--;

        if (Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end)))
            return false;

        start++;
        end--;
    }

    return true;
}