Match Alphanumerical Pattern in Matrix I

Match Alphanumerical Pattern in Matrix I

What is this problem about?

The Match Alphanumerical Pattern in Matrix I problem gives you a 2D board of numbers (digits 0-9) and a 2D pattern containing digits and lowercase English letters. You need to find if the pattern exists anywhere within the board. A pattern matches a subgrid if: all digits in the pattern exactly match the digits in the subgrid, and every identical letter in the pattern maps to exactly one identical digit in the subgrid, and vice-versa (a perfect 1-to-1 bijection).

Why is this asked in interviews?

This is a multi-layered matrix search problem. It tests two distinct skills: 2D Sliding Window (Subgrid Traversal) and Isomorphic String/Pattern Matching. Interviewers use it to see if a candidate can isolate the complex bijection logic into a helper function, rather than writing a massive, deeply nested and unreadable block of code.

Algorithmic pattern used

This problem relies on a Subgrid Iteration paired with a Bijection (Two Hash Maps) validation.

1. Iterate through every possible top-left coordinate (r, c) in the board where the pattern can fit without going out of bounds.
2. For each valid coordinate, pass the corresponding subgrid to a validation helper function.
3. The helper function maintains two Hash Maps (or arrays): letter_to_digit and digit_to_letter. As you compare the pattern cell to the subgrid cell, if the pattern is a digit, it must match exactly. If it's a letter, verify the 1-to-1 mapping using the two maps. If a contradiction occurs, the subgrid is invalid.

Example explanation

Board:

1 2
3 4

Pattern:

a a
3 4

Let's check the subgrid starting at (0,0).

• Compare pattern[0][0] ('a') with board[0][0] (1). Map 'a' -> 1, and 1 -> 'a'.
• Compare pattern[0][1] ('a') with board[0][1] (2). Check map: 'a' is already mapped to 1! But the board has 2. Contradiction! Match fails.

If the board top row was 1 1, the mapping for the second 'a' would see 'a' -> 1, which matches the board's 1. The validation would proceed to the second row, matching the digits exactly.

Common mistakes candidates make

The most frequent mistake is implementing only a one-way mapping (e.g., letter_to_digit). A true bijection requires checking both directions. If pattern is ['a', 'b'] and board is [1, 1], mapping 'a' -> 1 and 'b' -> 1 is valid under a one-way map, but fails the bijection rule because the digit 1 is mapped to two different letters. You MUST track digit_to_letter as well.

Interview preparation tip

When tackling the Match Alphanumerical Pattern in Matrix interview question, the "Isomorphic Strings" logic is the core hurdle. Practice writing a clean bijection checker using two arrays of size 256 (for ASCII). Because the subgrids are evaluated independently, always remember to clear or instantiate fresh Hash Maps inside your helper function for every new (r, c) starting coordinate you check.