Valid Palindrome - C Solution

1. Introduction

In this post, we explore how to determine if a string is a palindrome in C programming. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward, disregarding cases and non-alphanumeric characters. This problem is a classic example of string manipulation and validation.

Problem

Given a string s, determine if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters. The function should return true if s is a palindrome, or false otherwise.

2. Solution Steps

1. Sanitize the input string: convert it to lowercase and remove non-alphanumeric characters.

2. Use two pointers, one starting at the beginning of the string and the other at the end.

3. Move the pointers towards each other, comparing the characters at each position.

4. If all characters match, return true; otherwise, return false.

3. Code Program

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

// Function to check if a character is alphanumeric
int isAlphanumeric(char c) {
    return isalpha(c) || isdigit(c);
}

// Function to determine if the string is a palindrome
int isPalindrome(char* s) {
    int start = 0, end = strlen(s) - 1;

    while (start < end) {
        // Skip non-alphanumeric characters
        while (start < end && !isAlphanumeric(s[start])) start++;
        while (start < end && !isAlphanumeric(s[end])) end--;

        // Compare characters
        if (tolower(s[start]) != tolower(s[end])) {
            return 0; // Not a palindrome
        }

        start++;
        end--;
    }
    return 1; // Is a palindrome
}

// Main function to test the isPalindrome function
int main() {
    char s1[] = "A man, a plan, a canal: Panama";
    printf("Is Palindrome (Example 1): %s\n", isPalindrome(s1) ? "true" : "false");

    char s2[] = "race a car";
    printf("Is Palindrome (Example 2): %s\n", isPalindrome(s2) ? "true" : "false");

    char s3[] = " ";
    printf("Is Palindrome (Example 3): %s\n", isPalindrome(s3) ? "true" : "false");

    return 0;
}

Output:

Is Palindrome (Example 1): true
Is Palindrome (Example 2): false
Is Palindrome (Example 3): true

Explanation:

1. isAlphanumeric checks if a character is alphanumeric.

2. isPalindrome processes the string to determine if it's a palindrome.

3. Skip non-alphanumeric characters using two pointers.

4. Compare the characters after converting them to lowercase.

5. Return true if all characters match, false otherwise.

6. The main function tests the isPalindrome function with three examples and prints the results.