</>Ali · LeetCode
#0125·EasyTwo Pointers

Valid Palindrome

LeetCode #125 · Easy · Two Pointers · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Two Pointers

Strategy

  1. 1Use two pointers, one at the start and one at the end.
  2. 2Skip non-alphanumeric characters from both ends.
  3. 3Compare characters (case-insensitive) and move pointers inward.
  4. 4If any mismatch is found, return false.
Time
O(n)
Space
O(1)
Problem description(from LeetCode)

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.

Examples

Example 1
Input:
s = "A man, a plan, a canal: Panama"
Output:
true
Note:
"amanaplanacanalpanama" is a palindrome. Input: s = "race a car" Output: false

Constraints

  • •1 <= s.length <= 2 * 10^5
  • •s consists only of printable ASCII characters.

C++ Solution

solution.cpp
class Solution {
public:
bool isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    bool res = true;
    while (i < j) {
      if (!isalnum(s[i])) {
        i++;
        continue;
      }

      if (!isalnum(s[j])) {
        j--;
        continue;
      }

      if (tolower(s[i]) != tolower(s[j])) {
        res = false;
        break;
      }

      i++;
      j--;
    }

    return res;
  }
};

More Two Pointers problems