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: trueExample 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) —
loading...
Last Post: Coding Exercise - Remove Element - C++ - Online Judge
Next Post: Coding Exercise - Restore IP Addresses - C++ - Online Judge