-
Notifications
You must be signed in to change notification settings - Fork 0
040 — Valid Palindrome
LeetCode 125 · Easy. Given a string s, determine whether it's a palindrome after considering only alphanumeric characters and ignoring case.
Imagine checking whether a phrase carved onto a stone tablet reads the same forwards and backwards — except the stonemason sprinkled in random punctuation, spaces, and mixed the letter casing just to make your life difficult. You could first chisel out a clean copy with all the junk removed and every letter lowercased, then compare that clean copy to its own reverse. That works, but it means building an entire second (and third) tablet before you've even started comparing.
The sharper move: station one reader at the very first character and another at the very last. Each reader slides inward on their own, skipping past anything that isn't a letter or digit, and only stops to actually compare once both are standing on a "real" character. Lowercase both before comparing, since the tablet's casing was never meaningful. If the two readers ever disagree, it's not a palindrome. If they cross paths in the middle without ever disagreeing, it is — and no clean copy was ever built.
"Palindrome" is about as direct a signal as this vocabulary gets: any time a problem asks you to compare a sequence against its own mirror image, reach for one pointer walking in from the front and one walking in from the back, meeting in the middle. The extra clause here — "considering only alphanumeric characters, ignoring case" — doesn't change the pattern at all; it just means each pointer has to filter before it's allowed to compare.
Build a cleaned copy (lowercase letters and digits only), then compare it to its own reverse.
func isPalindromeBruteForce(_ s: String) -> Bool {
var cleaned = [Character]()
for char in s where char.isLetter || char.isNumber {
cleaned.append(Character(char.lowercased()))
}
return cleaned == cleaned.reversed()
}Big-O: O(n) time to build the cleaned array and compare it to its reverse. O(n) extra space, though — one full copy for cleaned, plus effectively another for the reversed comparison. The inefficiency here isn't in the time, it's in the two full-size allocations a two-pointer scan doesn't need.
Convert to an array once (Swift strings aren't random-access, so this single O(n) conversion is unavoidable), then walk two pointers inward from both ends. Each pointer skips non-alphanumeric characters on its own before a comparison happens.
func isPalindrome(_ s: String) -> Bool {
let chars = Array(s)
var left = 0
var right = chars.count - 1
while left < right {
while left < right && !chars[left].isLetter && !chars[left].isNumber {
left += 1
}
while left < right && !chars[right].isLetter && !chars[right].isNumber {
right -= 1
}
if chars[left].lowercased() != chars[right].lowercased() {
return false
}
left += 1
right -= 1
}
return true
}Big-O: O(n) time — each pointer visits every character at most once. O(n) space for the single Array(s) conversion, but O(1) additional space beyond that — no cleaned copy, no reversed copy, nothing else materialized.
Both approaches are O(n) time, so the win here isn't a Big-O time collapse like most Two Pointers problems — it's a space collapse. The brute force does its filtering as a separate, complete pass that produces a whole new array, then does a second complete pass to reverse-compare it. The two-pointer version fuses filtering and comparing into a single inward walk, checking each character "just in time" instead of pre-building anything. Not every brute-force-to-optimal jump in this pattern shrinks the time complexity — sometimes, as here, it shrinks the space complexity while the time bound stays put.
- Two Pointers — the converging-inward-pointers shape this solution is built on.
-
Arrays & Strings — the string being scanned, and why converting to
[Character]matters in Swift.
Valid Palindrome is two proofreaders starting at opposite ends of a scroll, skipping the punctuation, and meeting in the middle without ever writing anything down.
The optimal solution's two inner while loops (the ones that skip non-alphanumeric characters) both guard on left < right. Pick a concrete input string made up entirely of punctuation and spaces (no letters or digits at all) and walk through what would happen — infinite loop, or out-of-bounds crash — if that guard were removed from just the left-advancing loop.
⬅️ Previous: Longest Consecutive Sequence · Next: Two Sum II - Input Array Is Sorted ➡️