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.
1#include <iostream>
2#include <cctype>
3
4bool isPalindrome(std::string s) {
5 int left = 0, right = s.length() - 1;
6 while (left < right) {
7 while (left < right && !std::isalnum(s[left])) left++;
8 while (left < right && !std::isalnum(s[right])) right--;
9 if (std::tolower(s[left]) != std::tolower(s[right])) return false;
10 left++;
11 right--;
12 }
13 return true;
14}
15
16int main() {
17 std::string s = "A man, a plan, a canal: Panama";
18 if (isPalindrome(s)) {
19 std::cout << "true" << std::endl;
20 } else {
21 std::cout << "false" << std::endl;
22 }
23 return 0;
24}The C++ program uses similar logic to the C version but with C++ specific string operations and functions. It compares characters while skipping non-alphanumeric characters and ignoring case.
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.
1class Solution:
2 def
This Python solution filters the input to ignore non-alphanumeric characters and reverses the filtered string for comparison, aggressive and straightforward for detecting palindromes.