Leetcode: 125. Valid Palindrome

Checking Palindrome in C++

Here's a C++ code snippet that checks whether a given string is a palindrome:

class Solution {
public:
    bool isPalindrome(string s) {
        bool flag = true;
        for (int i = 0, j = s.size() - 1 ; i < s.size()/2 ; i++, j-- )
        {
            while (i < j && !isalnum(s[i]))
                i++;
            while (i < j && !isalnum(s[j]))
                j--;
            if (tolower(s[i]) != tolower(s[j]))
            {
                flag = false;
                break;
            }
        }
        return flag;
    }
};

    

Explanation

This code snippet defines a class named Solution with a member function isPalindrome. The function takes a string s as input and returns a boolean value indicating whether the string is a palindrome or not.

The code uses two pointers, i and j, initially pointing to the start and end of the string, respectively. It then iterates until i reaches the middle of the string, comparing characters at i and j to check for equality.

Within the loop, it skips non-alphanumeric characters by incrementing i if s[i] is not alphanumeric and decrementing j if s[j] is not alphanumeric.

If a mismatch between characters is found, the flag variable is set to false and the loop is terminated.

Finally, the function returns the value of the flag variable, indicating whether the string is a palindrome or not.

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the input string. The code iterates through the string once, comparing characters and skipping non-alphanumeric characters, resulting in a linear time complexity.

Example

Here's an example usage of the isPalindrome function:

Solution solution;
string input = "A man, a plan, a canal: Panama";
bool isPalindrome = solution.isPalindrome(input);
cout << (isPalindrome ? "Yes" : "No") << endl;

    

This will output Yes, indicating that the given input string is a palindrome.