💬 Discord
Sign In
NeetCode #177LC-125EasyTwo PointersBlind 75NC 150NC 250
← Back to All Problems

#177 · #125 · Valid Palindrome(验证回文串)

📌 Problem Statement & Constraints

A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forwards and backwards. Given a string s, return whether it is a palindrome. Constraints: 1 <= s.length <= 2 * 10^5; s consists of printable ASCII characters.

💡 Core Algorithmic Approaches

  1. Use two pointers, one at each end, and move them toward the middle.
  2. At each step, skip characters that are not alphanumeric on either side.
  3. Compare the lowercased characters; any mismatch means it is not a palindrome.
  4. Doing this in place avoids building a filtered copy of the string, so extra space is O(1).

💻 Benchmark Python3 Implementation

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1                     # skip non-alphanumeric
            while i < j and not s[j].isalnum():
                j -= 1
            if s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each pointer traverses the string once.
💾 Space Complexity
O(1) extra: no filtered copy is built, unlike the "".join(filter(str.isalnum, s)) approach which is O(n).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the inner i < j guards: the pointers can cross while skipping, causing an out-of-range index.
  • Using s[i].isalpha() instead of isalnum(): digits are also alphanumeric and must be kept.
  • Building a filtered string and reversing it: correct and short, but O(n) space. The two-pointer version is the expected optimisation.
  • Comparing without lowercasing: 'A' != 'a' in ASCII, so case must be normalised.