Valid Palindrome Leetcode Solution

Table of Contents

Problem Statement

Given a string, we have to determine if it is a palindrome, considering only alphanumeric characters i.e. numbers and alphabets only. We also have to ignore cases for alphabet characters.

Example

"A man, a plan, a canal: Panama"

true

Explanation:

“AmanaplanacanalPanama” is a valid palindrome.

"race a car"

false

Explanation:

“raceacar” is not a palindrome.

Naive Approach (Comparing with reverse)

To check if a string is palindrome or not we can simply reverse it and compare it with the original string. After reversing if it remains equal then the given string is a palindrome.
In this problem we have to ignore all the characters except alphabets and numbers. So for that we can filter the given string and save the filtered string in a new variable by removing all unwanted characters. Lets take an example:

We can see filtered string and reversed filtered string is not equal, hence it is not a valid palindrome.

Implementation for Valid Palindrome Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

bool isAlphaNum(char c)
{
    if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
        return true;
    return false;
}
    
char lowerCase(char c)
{
    if(65<=c && c<=90)
        return c+32;
    else 
        return c;
}
    
bool isPalindrome(string s) 
{
    string input;

    for(char c:s)
    {
        if(isAlphaNum(c))
            input+= lowerCase(c);
    }

    string reversed=input;
    reverse(reversed.begin(),reversed.end());

    if(input==reversed) return true;
    else return false;

}

int main() 
{
    string s="A man, a plan, a canal: Panama";
    if(isPalindrome(s))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}

true

Java Program

import java.lang.*;

class Rextester
{  
    static boolean isAlphaNum(char c)
    {
        if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
            return true;
        else
            return false;
    }
    
    static char lowerCase(char c)
    {
        if(65<=c && c<=90)
            return (char)(c+32);
        else 
            return c;
    }
    
    public static boolean isPalindrome(String s) 
    {
       StringBuffer buf= new StringBuffer();
        
       for(char c: s.toCharArray())
       {
           if(isAlphaNum(c))
               buf.append(lowerCase(c));
       }
        
        String input,reversed;
        input= buf.toString();
        reversed= buf.reverse().toString();
        
        if(input.equals(reversed))
            return true;
        else 
            return false;
        
    }
    
    public static void main(String args[])
    {
       String s="A man, a plan, a canal: Panama";
       System.out.println(isPalindrome(s));   
    }
}

true

Complexity Analysis for Valid Palindrome Leetcode Solution

Time Complexity

O(n): n is the length of the given string. We need to iterate the string linearly. Hence time complexity will be O(n).

Space Complexity

O(n): We need O(n) additional space to store the filtered string and the reversed string.

Optimized Approach (Using two pointers)

In above approach we filtered given string and used extra space to store it. We can also use two pointers for checking if it is a palindrome or not and we need not to filter or save it by creating extra memory.

1. What we can do is take two pointer variables, start and end and point them with the two ends of the input string.
2. Now move the start pointer to right so it points to a alphanumeric character. Similarly move end pointer to left so it also points to a alphanumeric character.
3. Now check if both the characters are same or not (ignoring cases):

If it is not equal then we know string is not a valid palindrome, hence return false.
Else continue to next iteration and repeat the same process of moving both pointers to point to next alphanumeric character till start<end.

4. After loop finishes, the string is said to be palindrome, hence return true.