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 <stdio.h>
2#include <ctype.h>
3#include <stdbool.h>
4
5bool isPalindrome(char *s) {
6 int left = 0, right = strlen(s) - 1;
7 while (left < right) {
8 while (left < right && !isalnum(s[left])) left++;
9 while (left < right && !isalnum(s[right])) right--;
10 if (tolower(s[left]) != tolower(s[right])) return false;
11 left++;
12 right--;
13 }
14 return true;
15}
16
17int main() {
18 char s[] = "A man, a plan, a canal: Panama";
19 if (isPalindrome(s)) {
20 printf("true\n");
21 } else {
22 printf("false\n");
23 }
24 return 0;
25}This C program reads characters from both ends of the string, moving pointers inward while ignoring non-alphanumeric characters. It checks for equality and converts characters to lowercase for case insensitivity. It returns false if a mismatch is found; otherwise, true.
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 isPalindrome
This Python solution filters the input to ignore non-alphanumeric characters and reverses the filtered string for comparison, aggressive and straightforward for detecting palindromes.