Valid Palindrome

Problem Source: LeetCode
Companies: Facebook, Microsoft, Apple, Oracle, Yandex, Bloomberg

Problem Statement:

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: “ab3 Gh h:g, 3ba”

Output: true

Example 2:

Input: “potato Tomato”

Output: false

Solution:

Using Two-pointers approach

Basic idea: The basic approach to solve a valid palindrome problem is that if you take it’s first half of that string and reverse it, you will find that it is exact equal to it’s second half.

For example: String = “rattar”.

Taking it’s first half (“rat”) and reversing it, becomes “tar” which is exact equal to the second half.

Algorithm:

A simple solution of this problem is that we just have to take two pointers (variables) initializing one with starting index of string and second with last index of that string.

We only have to check for alphanumeric characters ignoring other characters, so, from both ends we simply keeps on checking for the equality of the characters while traversing inwards, untill we reach at the middle of the given string.

The following steps should be taken for implementation:

1. Set two pointers i and j, one at each end of the given string s.
2. Ignoring other characters except for alphanumeric ones, checking the equality of the characters indexed at i and j, if this condition is not met at any point, break the whole loop and return with false statement.
3. Traverse inwards untill the pointers met in the middle.

Implementation

Java

public class Solution {
    public boolean isPalindrome(String s) {

        if (s == null ) return false;
        if (s.length() == 0) return true;

        s = s.toLowerCase(); // change all to lower case; 
        int i = 0;
        int j = s.length() - 1;

        while (i < j) {
            if (!(  (s.charAt(i) >= 'a' && s.charAt(i) <='z') || (s.charAt(i) >='0' && s.charAt(i) <= '9') )){
                i++;
                continue;
            }

            if (!(( s.charAt(j) >= 'a' && s.charAt(j) <='z') || (s.charAt(j) >='0' && s.charAt(j) <= '9'))){
                j--;
                continue;
            }

            if (s.charAt(i) == s.charAt(j)){
                i++;
                j--;
                continue;
            }

            if (s.charAt(i) != s.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool isPalindrome(string s) {

        if (s.size()==0)   {return true;}

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

        while (i<j){
            if (isalnum(s[i])==false){i++; continue;}
            if (isalnum(s[j])==false){j--; continue;}

            if (tolower(s[j])!=tolower(s[i])){
                return false;
            }else{
                i++;
                j--;
            }
        }

        return true;
    }
};

Python

class Solution:
    def isPalindrome(self, s: str) -> bool:

        i, j = 0, len(s) - 1

        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1

            if i < j and s[i].lower() != s[j].lower():
                return False

            i += 1
            j -= 1

        return True

Complexity Analysis:

• Time Complexity: Traversing is done for almost every character, untill the pointers meet in the middle or if the required condition is not true we return early. Time complexity will be O(n) (where n is the length of the given string).
• Space complexity: Since no extra space is being taken, space complexity is O(1).