LeetCode 10 · Hard · 2-D Dynamic Programming

Regular Expression Matching

The pattern p may use . for any one character and x* for zero or more copies of the character before it. Return whether p matches the whole of s.

O(m·n)time
O(m·n)space
x*: skip or usememo DFS on (i, j)

s: 1–8 lowercase letters · p: 1–8 of a–z, . and * · every * follows a letter or .

cache cell (i, j) = does p.substring(j) match s.substring(i) · → skip x* (j + 2) · ↓ x* eats s.charAt(i) · ↘ one char matched

Call stack bottom → top

public boolean isMatch(String s, String p) { Boolean[][] cache = new Boolean[s.length() + 1][p.length() + 1]; return dfs(0, 0, s, p, cache);}private boolean dfs(int i, int j, String s, String p, Boolean[][] cache) { if (cache[i][j] != null) { return cache[i][j]; } if (i >= s.length() && j >= p.length()) { return true; } if (j >= p.length()) { return false; } boolean match = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'); if (j + 1 < p.length() && p.charAt(j + 1) == '*') { cache[i][j] = dfs(i, j + 2, s, p, cache) // skip x* || (match && dfs(i + 1, j, s, p, cache)); // use x* return cache[i][j]; } if (match) { cache[i][j] = dfs(i + 1, j + 1, s, p, cache); return cache[i][j]; } cache[i][j] = false; return false;}
i, j
—
match
—
cache entries
0
memo hits
0

Why it works

  1. Brute force backtracks over how many characters each x* swallows. With several stars the choices multiply, and on inputs like "aaaaaaab" against "a*a*a*a*c" the work grows exponentially.
  2. Everything depends on (i, j): how much of s and of p is left. A star gives two moves: skip x* entirely (j + 2), or, if x matches s.charAt(i), let it eat that character and stay on the same star (i + 1). Without a star, one character must match and both move on.
  3. Complexity: (m+1)·(n+1) states, each solved once with O(1) work: O(m·n) time and space.
  4. Pitfall: look ahead at p.charAt(j + 1) before trying to match p.charAt(j): "c*" can match nothing even though 'c' does not match. And s running out is not failure: dfs(s.length(), j) can still succeed while the rest of p is all x* pairs.
  5. Related: Wildcard Matching (44) uses * as "any sequence" on its own, and the same table works with a simpler star rule.