Description

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.

Example 1:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: “amanaplanacanalpanama” is a palindrome.

Example 2:

Input: s = "race a car"

Output: false

Explanation: “raceacar” is not a palindrome.

Example 3:

Input: s = " "

Output: true

Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.

Solution:

If we think about how we would do it, we can say, replace all non-alphanumerical characters from the string with empty string, convert the string to lowercase string and then check each characters. The last step can also be replaced with reverse the string and verify the strings are matching.

This approach will work like this.

 1If string is null
 2    return true
 3Replace all non-alphanumeric characters with empty string
 4Convert uppercase to lowercase
 5Initialize two pointers left = 0, right = s.length() - 1
 6while left is less than right
 7    if s[left] != s[right]
 8        return false
 9    left++
10    right--
11return true

 1class Solution {
 2    public boolean isPalindromeBrute(String s) {
 3        if (s == null)
 4            return true;
 5        s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
 6        int left = 0, right = s.length() - 1;
 7        while (left < right) {
 8            if (s.charAt(left) != s.charAt(right))
 9                return false;
10            left++;
11            right--;
12        }
13        return true;
14    }
15}

Better Solution

This could be solved using two pointers approach. One pointer starts from the end and another from the beginning. In this case, we can initialize left = 0 and right = s.length() - 1. If the character we have found at left or right index is not alphanumeric, then we just move on to the next index using left++ or right--. If both characters are alphanumeric, then we make each of them lowercase and then compare if they are same. If they are not same, we right away return false. If they are same, we increment left pointer and decrement right pointer to check the next characters. Once we have checked all characters and if we didn’t find any mismatch, that means the string is palindrome.

 1If s = null or s = ""
 2    return true
 3Initialize two pointers left = 0, right = s.length() - 1
 4while left is less than right
 5    leftChar = left.toCharacter
 6    rightChar = right.toCharacter
 7    if (leftChar is not alphanumeric)
 8        left++
 9    else if (rightChar is not alphanumeric) 
10        right--
11    else 
12        if (leftChar.toLowerCase != rightChar.toLowerCase)
13            return false
14        left++
15        right--
16return true

 1class Solution {
 2    public boolean isPalindrome(String s) {
 3        if (s == null || s.trim().length() == 0)
 4            return true;
 5        int left = 0, right = s.length() - 1;
 6        while (left < right) {
 7            char leftChar = s.charAt(left);
 8            char rightChar = s.charAt(right);
 9            if (!Character.isLetterOrDigit(leftChar)) {
10                left++;
11            } else if (!Character.isLetterOrDigit(rightChar)) {
12                right--;
13            } else {
14                if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
15                    return false;
16                }
17                left++;
18                right--;
19            }
20        }
21        return true;
22    }
23}