Pattern Matching (Regex under the hood)

Concept

In production, if you need to check if a string matches a specific format (e.g., an email address), you use a Regular Expression (Regex).
However, in highly advanced interviews, you may be asked to implement a simplified version of a Regex engine yourself.

Problem: Given an input string s and a pattern p, implement regular expression matching with support for . and *.

• . Matches any single character.
• * Matches zero or more of the preceding element.

The Difficulty of *

If the pattern is "ab.d", the problem is easy. You just iterate through both strings simultaneously with two pointers. If s[i] === p[j] or p[j] === '.', you move both pointers forward.

The * character makes this problem incredibly hard.
Because * means “zero or more”, you have branching paths.
If s = "aaab" and p = "a*b":

• Does a* match zero ‘a’s?
• Does a* match one ‘a’?
• Does a* match all three ‘a’s?

To solve branching paths where future choices depend on previous choices, you must use Dynamic Programming or Backtracking (Recursion).

The Recursive Approach (Backtracking)

The cleanest way to explain the solution is through Recursion.

function isMatch(s: string, p: string): boolean {
    // Base Case: If pattern is empty, string must be empty to be a match
    if (p.length === 0) return s.length === 0;

    // Check if the current single character matches
    const firstMatch = s.length > 0 && (p[0] === s[0] || p[0] === '.');

    // Is the NEXT character a '*'? This completely changes the rules.
    if (p.length >= 2 && p[1] === '*') {
        // We have two branching choices:
        return (
            // Choice 1: The '*' matches ZERO characters. We skip the "a*" entirely.
            isMatch(s, p.substring(2)) ||
            // Choice 2: The '*' matches ONE character. We consume 1 char from the string 
            // and keep the "a*" in the pattern to see if it matches more!
            (firstMatch && isMatch(s.substring(1), p))
        );
    } else {
        // No '*' involved. Standard 1-to-1 match. Move both pointers forward.
        return firstMatch && isMatch(s.substring(1), p.substring(1));
    }
}

(Note: While elegant, this pure recursive approach generates a massive call stack and repeated string slicing, resulting in exponential $O(2^N)$ time complexity. In an interview, you would optimize this to $O(N \times M)$ using Top-Down Memoization or a 2D Dynamic Programming table).

Other Parsing Problems

Not all pattern matching involves Regex. Another massive category is String Parsing / Decoding.

Problem: Given an encoded string, return its decoded string. 3[a2[c]] -> accaccacc.

When a string has nested structures that must be resolved from the inside out (like brackets, parentheses, or math operations), you must almost always use a Stack.

You iterate through the string, pushing characters onto the Stack. When you encounter a closing bracket ], you start popping characters off the Stack until you find the opening bracket [, then you pop the number 3, multiply the string, and push the resolved result back onto the Stack.

Interview Questions

Q: You are asked to evaluate a mathematical string: "3 + 2 * 2". What data structure do you use?
A: A Stack.
Because of the Order of Operations (PEMDAS), you cannot just process the string strictly left to right (3+2=5, 5*2=10, which is wrong).
You iterate through the string. When you see a number, you evaluate the previous operator.
If the operator was +, you push the number to the stack. If the operator was *, you pop the top of the stack, multiply it by the new number, and push the result back.
At the end of the string, your stack looks like [3, 4]. You simply sum the remaining numbers in the stack to get the final answer (7).