The O(n) Club: Regular Expression Matching — When ‘.’ and ‘*’ Run the Show

The O(n) Club: Regular Expression Matching — When ‘.’ and ‘*’ Run the Show

⚡ TL;DR

Match string s against pattern p composed of lowercase letters, . (any single char), and * (zero or more of preceding element). Full match only; substring freeloaders not welcome. Naive recursion is a trap. DP/memoization is your lifeline:

// Minimal flavor Java: check s against p
boolean isMatch(String s, String p) {
    Boolean[][] memo = new Boolean[s.length()+1][p.length()+1];
    return dp(s, p, 0, 0, memo);
}

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

Think of p as a painfully literal robot with a barcode scanner: . happily beeps any single thing through; * hangs out as long as you want, but only if you scan the exact same item repeatedly. Full-pattern match means you can’t just show up, scan “beep”, and hide the rest in your backpack—the scanner must process every item, in order, no smuggling!

The only way to survive this is dynamic programming: For each position i, j, memoize whether s[i:] exactly matches p[j:]. If you don’t, you’ll be stuck in Turing’s purgatory, reliving overlapping subproblems forever.

🛠️ PseudoCode

• Base Case: If both s and p are exhausted: match = true. If pattern runs out first, game over.
• First Match Check:

  boolean firstMatch = (i < s.length()) && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');

• Star Handling: If pattern has a * at j+1:
  • Skip star entirely (zero of previous char): dp(i, j+2)
  • Or, if firstMatch, eat one character and try again with same star: dp(i+1, j)

  if (j+1 < p.length() && p.charAt(j+1) == '*') {
    return dp(i, j+2) || (firstMatch && dp(i+1, j));
  }

• No Star: Regular char/dot: advance both pointers if firstMatch.

  else { return firstMatch && dp(i+1, j+1); }

• Memoize Everything: Save the result at memo[i][j] before returning!

💻 The Code

// Top-down memoization approach
public boolean isMatch(String s, String p) {
    Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
    return dp(s, p, 0, 0, memo);
}
 private boolean dp(String s, String p, int i, int j, Boolean[][] memo) {
    if (memo[i][j] != null) return memo[i][j];
    boolean ans;
    if (j == p.length()) {
        ans = i == s.length();
    } else {
        boolean firstMatch = (i < s.length()) &&
            (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            ans = dp(s, p, i, j + 2, memo) || (firstMatch && dp(s, p, i + 1, j, memo));
        } else {
            ans = firstMatch && dp(s, p, i + 1, j + 1, memo);
        }
    }
    memo[i][j] = ans;
    return ans;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge sneaks: a* matches "" and as many as as you want. .* matches… well, everything (if your pattern covers all of s!). *a? Not allowed—even this regex has standards.
• Don’t partial-match: ab* will not match "ba". We’re not running a soup kitchen here.
• Performance: Time/space is O(N*M)—as fun as it gets for this puzzle. Anything dumber will have your CPU on strike.
• Gotchas: Fiddly off-by-one bugs—careful when inputs hit the end!

🧠 Interviewer Brain-Tattoo

“Treat * like a clingy clone machine, not a genie. Abuse DP and memoization, and the only thing exploding will be your interviewer’s admiration.”