Table of contents


Given 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:
    Input: "A man, a plan, a canal: Panama"
    Output: true

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

Constraints:

  • s consists only of printable ASCII characters.


Using recursive version

public static boolean isPalindrome0(String s) {
    int left = 0;
    int right = s.length() - 1;

    return isPalindrome0(s, left, right);
}

public static boolean isPalindrome0(String s, int left, int right) {
    if (left >= right) {
        return true;
    }

    while (!Character.isLetterOrDigit(s.charAt(left))) {
        ++left;
    }

    while (!Character.isLetterOrDigit(s.charAt(right))) {
        --right;
    }

    if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
        return false;
    }

    return isPalindrome0(s, ++left, --right);
}

The complexity of this solution:

  • Time complexity: O(n)
  • Space complexity: O(n)


Using Two-Pointers technique

Based on the definition of palindrome string, so we can use two pointers technique to solve it.

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) {
        char leftChar = s.charAt(left);
        char rightChar = s.charAt(right);
        
        if (!Character.isLetterOrDigit(leftChar)) {
            ++left;
            continue;
        }
        
        if (!Character.isLetterOrDigit(rightChar)) {
            --right;
            continue;
        }
        
        if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
            return false;
        } else {
            ++left;
            --right;
        }
    }
    
    return true;
}

The complexity of this solution:

  • Time complexity: O(n)
  • Space complexity: O(1)


Wrapping up

  • Understanding the traits that we can apply two pointers technique.


Refer:

https://leetcode.com/problems/valid-palindrome/

https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/549/week-1-august-1st-august-7th/3411/