Valid Palindrome

Solution

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

 

Examples

 

Explanation

class Solution {
    public boolean isPalindrome(String s) {
        String newS =s.toLowerCase().replaceAll("[^a-z0-9]", "");
        int i = 0, j = newS.length() - 1;
        while(i < j){
            if(newS.charAt(i)!=newS.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

 

This is how I solve the problem.

 

1. The input string s is converted to lowercase, and all non-alphanumeric characters are removed to create a new string newS.

 

2. Two pointers, i and j, are used to compare characters from the front and back of the string.

 

3. If the characters at the two pointers are different, the method returns false. If they are the same, both pointers are moved inward.

 

4. If all characters are the same, the method returns true.

 

class Solution {
    public boolean isPalindrome(String s) {
        if(s.isEmpty()) return true;

        int i = 0, j = s.length() - 1;
        while(i < j){
            char front = s.charAt(i);
            char back = s.charAt(j);
            if(!Character.isLetterOrDigit(front)) i++;
            else if(!Character.isLetterOrDigit(back)) j--;
            else{
                if(Character.toLowerCase(front) != Character.toLowerCase(back)) return false;
                i++;
                j--;
            }
        }
        return true;
    }
}

 

1. Empty String Handling: If the input string s is empty, the method immediately returns true, since an empty string is considered a palindrome.

 

2. Two-Pointer Algorithm: Pointers i and j are used to inspect characters from both ends of the string.

 

3. Character Check: Each pointer checks whether the character it points to is an alphanumeric character. If not, the respective pointer is either incremented or decremented.

 

4. Comparison Logic: If both characters are alphanumeric, they are converted to lowercase and compared. If they are not the same, the method returns false.

 

5. Final Result: If all checks are completed without finding any discrepancies, the method returns true.

 

 

The first code creates a new string, leading to higher space complexity. In contrast, the second code directly inspects the input string, avoiding unnecessary space usage and improving time complexity since each character is checked only once.