How to Perform Case-insensitive Valid Palindrome AlphaNum String Check?


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: “A man, a plan, a canal: Panama”
Output: true

Example 2:
Input: “race a car”
Output: false

Check if a given string is a valid palindrome but ignore characters other than Uppercase, Lowercase and Digits (alphanumeric). The comparison is case-insensitive. The empty string is defined as a valid palindrome.

First step, it is easy to check if any character is one of the alphanumeric characters.

1
2
3
4
5
6
    
inline bool chk(char a) {
        return ((a >= 'a') && (a <= 'z')) ||                 
               ((a >= 'A') && (a <= 'Z')) ||                 
               ((a >= '0') && (a <= '9')) ;
}
    
inline bool chk(char a) {
        return ((a >= 'a') && (a <= 'z')) ||                 
               ((a >= 'A') && (a <= 'Z')) ||                 
               ((a >= '0') && (a <= '9')) ;
}

The ASCII codes between any upper-case letter and its lower-case or vice versa is 32. For example, ‘A’ is 65 while ‘a’ is 97. So we can use that when comparing letters.

Two index pointers, starting from the beginning and the end respectively, skip non-alphanumeric letters. The function immediately returns false once it finds a mismatch, or otherwise it gives a true answer when two index pointers meet each other in the middle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        if (n == 1) return true;
        int i = 0, j = n - 1;
        while (i <= j) { // two pointers not met yet
            // ignore other characters from beginning
            while ((i <= j) && (!chk(s[i]))) i ++;              
            // ignore other characters from end             
            while ((j >= i) && (!chk(s[j]))) j --; 
            // not equal return invalid
            if ((i < j) && (s[i] != s[j]) && (s[i] != s[j] + 32) && (s[j] != s[i] + 32)) return false;
            i ++;
            j --;
        }
        return true;
    }
};
class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        if (n == 1) return true;
        int i = 0, j = n - 1;
        while (i <= j) { // two pointers not met yet
            // ignore other characters from beginning
            while ((i <= j) && (!chk(s[i]))) i ++;              
            // ignore other characters from end             
            while ((j >= i) && (!chk(s[j]))) j --; 
            // not equal return invalid
            if ((i < j) && (s[i] != s[j]) && (s[i] != s[j] + 32) && (s[j] != s[i] + 32)) return false;
            i ++;
            j --;
        }
        return true;
    }
};

The above seems a bit verbose. In C++, you can use the isalnum() method to check if a character is digit (isdigit) or alpha characters (isalpha). And we can use std::toupper or std::tolower to perform case insensitive comparisons.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isPalindrome(string s) {
        if (s.size() == 0) return true;
        int i = 0, j = s.size() - 1;
        while (i < j) {
            while ((i < j) && (!isalnum(s[i]))) ++i;
            while ((i < j) && (!isalnum(s[j]))) --j;
            if (std::toupper(s[i]) != std::toupper(s[j])) return false;
            i ++;
            j --;
        }
        return true;
    }
};
class Solution {
public:
    bool isPalindrome(string s) {
        if (s.size() == 0) return true;
        int i = 0, j = s.size() - 1;
        while (i < j) {
            while ((i < j) && (!isalnum(s[i]))) ++i;
            while ((i < j) && (!isalnum(s[j]))) --j;
            if (std::toupper(s[i]) != std::toupper(s[j])) return false;
            i ++;
            j --;
        }
        return true;
    }
};

Javascript Function to Determine Valid Palindrome String Skipping WhiteSpaces and Ignoring Cases

Here is the Javascript Implementation of the same Palindrome algorithm. We define a local function using Arrow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    const isAlphaNum = x => {
        return ((x >= 'A') && (x <= 'Z')) ||
            ((x >= 'a') && (x <= 'z')) ||
            ((x >= '0') && (x <= '9'));
    }
    if (s === "") return true;
    const len = s.length;
    let i = 0, j = len - 1;
    while (i < j) {
        while ((i < j) && (!isAlphaNum(s.charAt(i)))) i ++;
        while ((i < j) && (!isAlphaNum(s.charAt(j)))) j --;
        if (s.charAt(i).toUpperCase() != s.charAt(j).toUpperCase()) return false;
        i ++;
        j --;
    }
    return true;
};
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    const isAlphaNum = x => {
        return ((x >= 'A') && (x <= 'Z')) ||
            ((x >= 'a') && (x <= 'z')) ||
            ((x >= '0') && (x <= '9'));
    }
    if (s === "") return true;
    const len = s.length;
    let i = 0, j = len - 1;
    while (i < j) {
        while ((i < j) && (!isAlphaNum(s.charAt(i)))) i ++;
        while ((i < j) && (!isAlphaNum(s.charAt(j)))) j --;
        if (s.charAt(i).toUpperCase() != s.charAt(j).toUpperCase()) return false;
        i ++;
        j --;
    }
    return true;
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
593 words
Last Post: Coding Exercise - Remove Element - C++ - Online Judge
Next Post: Coding Exercise - Restore IP Addresses - C++ - Online Judge

The Permanent URL is: How to Perform Case-insensitive Valid Palindrome AlphaNum String Check?

Leave a Reply