Mirror Phrase Check
EasyTwo PointersFree
Problem
A word-game app wants to accept phrases that read the same forwards and backwards. Before comparing, the app ignores every character that is not an ASCII letter or digit, and treats uppercase and lowercase letters as equal.
Given a string s, return true if it is a mirror phrase under those rules and false otherwise.
Example 1
- Input:
- s = "Was it a car, or a cat I saw?"
- Output:
- true
Keeping only letters and digits in lowercase gives "wasitacaroracatisaw", which is the same reversed.
Example 2
- Input:
- s = "Step on no pets!"
- Output:
- true
Example 3
- Input:
- s = "0P"
- Output:
- false
"0p" reversed is "p0".
Constraints
- 0 ≤ s.length ≤ 2·10^5
- s contains printable ASCII characters only
Hint
Show the first hint
A palindrome check compares the first character with the last, the second with the second-to-last, and so on.
Walkthrough
How to approach it
01Clarify before coding
- Which characters count? Only ASCII letters and digits; spaces, punctuation and underscores are ignored.
- Is the comparison case-sensitive? No, 'A' and 'a' are equal.
- What about an empty string or a string with no letters or digits? Both are mirror phrases: there is nothing that fails to match.
02Brute force
Build a new string with only the lowercase letters and digits, reverse it, and compare the two.
Cost: O(n) time but O(n) extra space for the cleaned copy and its reverse; correct, but the interviewer will ask for O(1) space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.