Mirror Phrase Contest

Easytwo pointersAlso known as Valid Palindrome

A word-puzzle club runs a contest for phrases that read the same forwards and backwards. People send entries like "Top spot." and "12:21". The judges only look at letters and digits. Spaces, commas, colons and other marks do not count, and capital letters count the same as small ones.

So "Top spot." is judged as topspot, which mirrors perfectly. The club gets thousands of entries and wants a program to do the first round of judging.

Your task

Write isMirrorPhrase(entry). Return true if the letters and digits of entry, read left to right, are the same as read right to left, ignoring case. Return false otherwise.

Every character that is not a letter (a-z, A-Z) or a digit (0-9) is ignored. Digits count and must mirror like letters. An entry with no letters or digits at all counts as a mirror phrase.

isMirrorPhrase(entry: string) → bool

Examples

Example 1

Input

entry = "Top spot."

Output

true

Why

Keep only letters and digits, all lowercase: topspot. Read backwards it is still topspot, so the entry passes.

Example 2

Input

entry = "Step on pets"

Output

false

Why

The letters are steponpets. Backwards that is stepnopets. The ends match for a while (s and s, t and t, e and e, p and p), but then o meets n, so it fails.

Example 3

Input

entry = "0P"

Output

false

Why

Digits count. The characters are 0 and p, which are different. If you threw digits away you would be left with just p and wrongly answer true.

Constraints

0 ≤ entry.length ≤ 2,000
entry contains printable ASCII characters only (letters, digits, spaces, punctuation).

Start with brute force

Build a cleaned copy with only the letters and digits in lowercase, make a reversed copy, and compare the two strings.

This is correct and runs in O(n), so it is fine at this size. Its cost is memory: it builds two extra strings as long as the input. Checking from both ends in the original string needs no copies at all, and it can stop at the first mismatch instead of cleaning the whole entry first.

Hints

0 of 4 shown

Hint 1
Take "Top spot.". Which character must the first T match? Where is it, and what did you skip to reach it?
Hint 2
A mirror phrase is checked from both ends at once: the first counted character against the last, the second against the second last, and so on.
Hint 3
Put one finger at the start and one at the end. If a finger is on a space or a mark, move just that finger inward and look again.
Hint 4
Use left and right indexes. Skip characters that are not letters or digits. When both point at real characters, compare them in lowercase: if they differ, the answer is false; if they match, move both inward. Stop when they meet.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

A mirror phrase pairs its first counted character with its last, its second with its second last, and so on. So check the pairs directly, from both ends of the original string, and skip anything that does not count.

Trace "Top spot." (indexes 0 to 8):

left = 0 (T), right = 8 (.). The period does not count. Move right to 7.
T and t: equal in lowercase. Move both: left = 1, right = 6.
o and o: equal. left = 2, right = 5.
p and p: equal. left = 3, right = 4.
left is on the space. Skip it: left = 4. Now left = right, so the loop ends. Every pair matched: return true.

The middle character never needs a partner, which is why the loop stops when the two indexes meet. Each step moves at least one index inward, so there are at most n steps.

Reference solution

function isMirrorPhrase(entry) {
  const counts = (ch) => /[a-z0-9]/i.test(ch);
  let left = 0, right = entry.length - 1;
  while (left < right) {
    if (!counts(entry[left])) { left++; continue; }
    if (!counts(entry[right])) { right--; continue; }
    if (entry[left].toLowerCase() !== entry[right].toLowerCase()) return false;
    left++;
    right--;
  }
  return true;
}

def is_mirror_phrase(entry):
    left, right = 0, len(entry) - 1
    while left < right:
        if not entry[left].isalnum():
            left += 1
        elif not entry[right].isalnum():
            right -= 1
        elif entry[left].lower() != entry[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

TimeO(n)Every step moves one or both indexes inward, so the loop runs at most n times.

SpaceO(1)Two indexes. No cleaned or reversed copy.

Learn the idea: Two Pointers Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code