Valid Palindrome - CPP Solution

1. Introduction

This post delves into a classic problem in string processing: determining whether a given string is a palindrome. We explore how to validate a palindrome in C++ after normalizing the string by converting it to lowercase and removing all non-alphanumeric characters.

Problem

Given a string s, the task is to determine whether it is a palindrome. A string is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include both letters and numbers.

2. Solution Steps

1. Normalize the string: convert all characters to lowercase and remove non-alphanumeric characters.

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

3. Compare the characters at these two pointers.

4. If the characters are different, return false.

5. Move the pointers towards each other and repeat the comparison.

6. If the pointers cross each other, return true.

3. Code Program

#include <iostream>
#include <cctype>
using namespace std;

// Function to check if a string is a palindrome
bool isPalindrome(string s) {
    int start = 0, end = s.size() - 1;

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

        // Compare characters
        if (tolower(s[start]) != tolower(s[end])) {
            return false; // Not a palindrome
        }
        start++; end--;
    }
    return true; // String is a palindrome
}

int main() {
    string s = "A man, a plan, a canal: Panama";
    cout << "Is palindrome: " << isPalindrome(s) << endl;
    return 0;
}

Output:

Is palindrome: 1

Explanation:

1. The input string "A man, a plan, a canal: Panama" is processed for palindrome check.

2. Non-alphanumeric characters are ignored, and characters are compared in a case-insensitive manner.

3. The function checks each pair of characters from the start and end, moving towards the middle.

4. If all pairs match, the string is identified as a palindrome.

5. The function returns true (represented as 1) since the normalized string is indeed a palindrome.