Sponsored
Sponsored
This approach employs two pointers: one starting at the beginning of the string and the other at the end. The algorithm checks if the characters at these pointers are the same, ignoring case and non-alphanumeric characters. If they match, both pointers move inward. If they don't or if any pointer surpasses the other, the string is not a palindrome.
Time Complexity: O(n), where n is the length of the string, because we go through the string at most once.
Space Complexity: O(1), as we use a constant amount of space.
1const isPalindrome = function(s) {
2 let left = 0, right = s.length - 1;
3 while (left < right) {
4 while (left < right && !(/[a-zA-Z0-9]/).test(s[left])) left++;
5 while (left < right && !(/[a-zA-Z0-9]/).test(s[right])) right--;
6 if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
7 left++;
8 right--;
9 }
10 return true;
11};
12
13// Test
14console.log(isPalindrome("A man, a plan, a canal: Panama"));The JavaScript solution utilizes regular expressions to test character validity and performs similar checks to other languages, ensuring characters from both ends match when lowered for case invariance.
This approach first cleans the input string by removing non-alphanumeric characters and converting all letters to lowercase. It then compares the normalized string to its reverse to determine if it is a palindrome.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), because the cleaned string and its reverse require extra space proportional to n.
1#include <iostream>
2#include <string>
3#include <algorithm>
4#include <cctype>
bool isPalindrome(std::string s) {
std::string filtered = "";
for (char c : s) {
if (std::isalnum(c)) {
filtered += std::tolower(c);
}
}
std::string reversed = filtered;
std::reverse(reversed.begin(), reversed.end());
return filtered == reversed;
}
int main() {
std::string s = "A man, a plan, a canal: Panama";
if (isPalindrome(s)) {
std::cout << "true" << std::endl;
} else {
std::cout << "false" << std::endl;
}
return 0;
}This C++ solution constructs a cleaned version of the input, removing non-alphanumeric characters and converting them to lowercase. It checks if this cleaned string equals its reverse.