Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
A palindrome is a word, phrase, number, or other sequences of characters that reads the same forward and backward, disregarding any non-alphanumeric characters.
You may assume that the input string s contains only printable ASCII characters.
Table of Contents
Sample Input and Expected Output:
Input:
s = "A man, a plan, a canal: Panama"
Output:
The string is a valid palindrome.
Input:
s = "race a car"
Output:
The string is not a valid palindrome.
Valid Palindrome Solution in C++:
The idea is to use two pointers, one starting from the beginning of the string and the other starting from the end of the string. We compare the characters at these pointers while ignoring non-alphanumeric characters and considering the case-insensitivity. If all characters match, the string is a valid palindrome.
#include <iostream>
#include <cctype> // For the isalnum() and tolower() functions
bool isPalindrome(std::string s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
// Skip non-alphanumeric characters from the left side.
while (left < right && !std::isalnum(s[left])) {
left++;
}
// Skip non-alphanumeric characters from the right side.
while (left < right && !std::isalnum(s[right])) {
right--;
}
// Compare characters (ignoring case) at the left and right pointers.
if (std::tolower(s[left]) != std::tolower(s[right])) {
return false; // Not a palindrome
}
left++;
right--;
}
return true; // The string is a palindrome
}
int main() {
std::string s1 = "A man, a plan, a canal: Panama";
std::string s2 = "race a car";
bool result1 = isPalindrome(s1);
bool result2 = isPalindrome(s2);
std::cout << "The string is " << (result1 ? "a valid palindrome." : "not a valid palindrome.") << std::endl;
std::cout << "The string is " << (result2 ? "a valid palindrome." : "not a valid palindrome.") << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(n), where n is the length of the input string s. The two-pointer approach allows us to traverse the string only once.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input string.