125. Valid Palindrome.md

125. Valid Palindrome

1. Description

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Constraints:

• s consists only of printable ASCII characters.

2. Solutions

Solution 1: Language: C Two Pointers

The resulting algorithm is simple:

• Set two pointers, one at each end of the input string
• If the input is palindromic, both the pointers should point to equivalent characters, at all times.
  • If this condition is not met at any point of time, we break and return early.
• We can simply ignore non-alphanumeric characters by continuing to traverse further.
• Continue traversing inwards until the pointers meet in the middle.

• Wednesday, 28 October, 2020
• Time Complexity: $O(n)$
• Space Complexity: $O(1)$
• Runtime: 0 ms, faster than 100.00% of C online submissions for Valid Palindrome.
• Memory Usage: 6.3 MB, less than 20.70% of C online submissions for Valid Palindrome.

// isalnum() checks whether the argument is an alphanumeric character or not.
// tolower() convert the argument to a lowercase character.
bool isPalindrome(char *s) {
    int head = 0;
    int tail = strlen(s) - 1;
    while (head < tail) {
        // Check the condition `head < tail` to avoid the runtime error.
        while (head < tail && !isalnum(s[head])) {
            head++;
        }
        // Check the condition `head < tail` to avoid the runtime error.
        while (head < tail && !isalnum(s[tail])) {
            tail--;
        }
        if (tolower(s[head]) != tolower(s[tail])) {
            return false;
        }
        head++;
        tail--;
    }
    return true;
}