Valid Palindrome – Leetcode #125

Problem Statement

This problem is from Leetcode – Valid Palindrome. The problem statement in short is as below:

Given a string s, return true if it is a palindrome after converting to lowercase and removing all non-alphanumeric characters; otherwise, return false.

Solution

This problem is asking us to check whether the given string is a palindrome or not – after removing all non-alphanumeric characters.

1. First remove all non-alphanumeric characters from the string.
2. Next remove all spaces from the string.
3. Now in a for loop compare the respective characters from both ends of the string. If any comparison fails then exit with false.

Lets see the code sample below:

public boolean isPalindrome(String s) {
		
		boolean isPalin = true;
		
		// remove all non-alphanumeric characters
		s = s.replaceAll("[^A-Za-z0-9]", "");
		
		// remove spaces
		s = s.replace(" ", "");
		
		// convert string to lower case
		s = s.toLowerCase();
		
		// if the length of string here is zero then return true 
		if(s.length() == 0) {
			
			return isPalin;
		}
		
		// get the mid-point of the string length 
		int index = s.length() / 2;
		
		// compare the respective characters from both ends of the string till mid-point
		for(int i=0; i<=index; i++) {
			
			if( s.charAt(i) != s.charAt(s.length()-1-i)) {
				
				isPalin = false;
				break;
			}
		}
		
		return isPalin;
        
    }

You can checkout the code from Github here: Valid Palindrome

PERFORMANCE ANALYSIS

RUNTIME	14 ms | Beats 32.00 %
MEMORY	45.72 MB | Beats 12.67 %
TIME COMPLEXITY	O (N)