[LeetCode] 125. Valid Palindrome

Posted on | In

Problem

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 1:

1
2
Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

1
2
Input: "race a car"
Output: false

Explanation

  1. We can use a left and right poitner pointing to the beginning and the end of the string respectivly, and compare their character. If the character is pointing at is not a letter or digit, then we skip it; else if the character is not match, then we return false; else if they are matched, then we move left pointer to the right, right pointer to the left. Repeat it until left pointer is equal or greater than right pointer.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public boolean isPalindrome(String s) {
        if (s.length() == 0) return true;
        s = s.trim();
        char[] arr = s.toCharArray();
        int left = 0, right = arr.length-1;
        while(left < right) {
            if (!Character.isLetterOrDigit(arr[left])) left++;
            else if (!Character.isLetterOrDigit(arr[right])) right--;
            else if (Character.toLowerCase(arr[left]) != Character.toLowerCase(arr[right])) return false;
            else {
                left++;
                right--;
            }
        }

        return true;
    }
}


// class Solution {
//     public boolean isPalindrome(String s) {
//         if (s.length() == 0) return true;
//         s = s.trim();
//         s = s.toLowerCase();
//         StringBuilder sb = new StringBuilder();
//         for (char c : s.toCharArray()) {
//             if (Character.isLetterOrDigit(c)) {
//                 sb.append(c);
//             }
//         }
//         s = sb.toString();
//         char[] arr = s.toCharArray();
//         for (int i = 0; i < arr.length; i++) {
//             if (arr[i] != arr[arr.length-i-1]) {
//                 return false;
//             }
//         }
//         return true;
//     }
// }