Regular Expression Matching

Regular Expression Matching is the kind of question that decides between a “good” and a “great” rating. It mixes string logic with the tricky star symbol. Many people freeze on the star. But once you split the star into its two simple meanings, the whole thing turns into a friendly grid you fill in one cell at a time.

🎯 The Problem

You get a text string and a pattern string, and you decide if the pattern matches the whole text.

• A dot . matches any single character. It stands in for exactly one letter.
• A star * matches zero or more of the character right before it.
• So a* can mean no a at all, or one a, or many as.
• The match must cover the entire text, not just a piece of it.

The star is the part that catches people, because it can match nothing.

Input:  text = "aab", pattern = "c*a*b"
Output: true

Explanation:
  c* matches zero c's
  a* matches two a's (the "aa")
  b  matches the final b

Let us also see a false case. With text = "mississippi" and pattern = "mis*is*p*." the answer is false. The pattern runs out of room to cover all the letters. So matching the whole string is the strict rule here.

Here is the picture of the question. The text along one side, the pattern along the other, asking if they line up fully.

🐢 Approach 1: Plain Recursion (Brute Force)

Compare from the front, one character at a time, branching on each star.

The idea:

• Look at the first letter of the text and the first symbol of the pattern.
• A normal symbol or dot must match the current text letter, then move both forward.

How it works:

• When the next pattern symbol is a star, you face a fork.
• The star matches zero copies, so skip the pattern letter and its star, keep the same text.
• Or the star matches one more copy, so if letters line up, eat one text letter and keep the star.

Why it is weak:

• The star keeps splitting into two paths over and over.
• The same text-and-pattern position gets visited many times.
• The work grows exponentially. Too slow for long inputs.

Here is the plain recursion code:

def is_match(s, p):
    def dfs(i, j):
        if j == len(p):
            return i == len(s)
        first = i < len(s) and p[j] in {s[i], "."}
        if j + 1 < len(p) and p[j + 1] == "*":
            return dfs(i, j + 2) or (first and dfs(i + 1, j))
        return first and dfs(i + 1, j + 1)

    return dfs(0, 0)

⚡ Approach 2: Add Memoization (Better)

Save each (i, j) position so it is solved only once.

The idea:

• i is how far we are in the text and j is how far we are in the pattern.
• The same position gets re-solved again and again in plain recursion.

How it works:

• Store the answer for each (i, j) the first time you compute it.
• Reach the same position again, read it from the store instead of redoing the work.

Why it is fast:

• Memoization caches a result so the same call never runs twice.
• There are about m × n positions, each solved once. Time drops to O(m × n).

Here is the memoized recursion:

from functools import lru_cache


def is_match(s, p):
    @lru_cache(None)
    def dfs(i, j):
        if j == len(p):
            return i == len(s)
        first = i < len(s) and p[j] in {s[i], "."}
        if j + 1 < len(p) and p[j + 1] == "*":
            return dfs(i, j + 2) or (first and dfs(i + 1, j))
        return first and dfs(i + 1, j + 1)

    return dfs(0, 0)

🚀 Approach 3: Bottom-Up 2D DP Table (Best)

Fill a yes/no grid from the simplest cases up, with no recursion.

The idea:

• Make a grid dp with one extra row and one extra column.
• dp[i][j] is true if the first i text letters match the first j pattern symbols.

How the borders work:

• dp[0][0] is true, because an empty text matches an empty pattern.
• The first row is the empty text against the pattern.
• A pattern like a*b* can still match an empty text when each star takes zero copies.
• So when pattern[j-1] is a star, dp[0][j] = dp[0][j-2].

The main rule (look at text letter i-1 and pattern symbol j-1):

• A normal letter or dot must match, so dp[i][j] copies dp[i-1][j-1] when they line up.
• A star splits into two meanings.
• Zero copies: look two symbols back with dp[i][j-2].
• One more copy: only when the letter before the star matches, then look up with dp[i-1][j].
• If either star branch is true, the cell is true.

Why it is best:

• Each of the m × n cells is filled once. Time is O(m × n).
• Two loops, no recursion stack.

Here is the filled table for text = "aab" and pattern = "c*a*b". The bottom-right cell holds the answer, which is true, shown as 1.

Steps to Solve

1. Let m be the text length and n be the pattern length. Make a grid dp of size m+1 by n+1, all false.
2. Set dp[0][0] to true, since empty text matches empty pattern.
3. Fill the first row. When pattern[j-1] is a star, set dp[0][j] = dp[0][j-2].
4. For each cell, if pattern[j-1] is a star, set it true if dp[i][j-2] is true, or if the char before the star matches text[i-1] and dp[i-1][j] is true.
5. If pattern[j-1] is a dot or equals text[i-1], copy dp[i-1][j].
6. The answer is dp[m][n].

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isMatch(const char *s, const char *p) {
    int m = (int)strlen(s);
    int n = (int)strlen(p);
    bool dp[64][64] = {{false}};

    dp[0][0] = true;                       // empty text, empty pattern

    for (int j = 1; j <= n; j++) {         // empty text vs pattern
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];       // star matches zero copies
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p[j - 1];
            if (pc == '*') {
                char before = p[j - 2];
                bool zero = dp[i][j - 2];               // star = zero copies
                bool more = (before == s[i - 1] || before == '.')
                            && dp[i - 1][j];            // star = one more copy
                dp[i][j] = zero || more;
            } else if (pc == '.' || pc == s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];             // single match
            }
        }
    }
    return dp[m][n];
}

int main(void) {
    const char *text = "aab";
    const char *pattern = "c*a*b";
    printf("%s\n", isMatch(text, pattern) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isMatch(const string& s, const string& p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    dp[0][0] = true;                       // empty text, empty pattern

    for (int j = 1; j <= n; j++) {         // empty text vs pattern
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];       // star matches zero copies
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char pc = p[j - 1];
            if (pc == '*') {
                char before = p[j - 2];
                bool zero = dp[i][j - 2];                // star = zero copies
                bool more = (before == s[i - 1] || before == '.')
                            && dp[i - 1][j];             // star = one more copy
                dp[i][j] = zero || more;
            } else if (pc == '.' || pc == s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];             // single match
            }
        }
    }
    return dp[m][n];
}

int main() {
    string text = "aab";
    string pattern = "c*a*b";
    cout << (isMatch(text, pattern) ? "true" : "false") << endl;
    return 0;
}

true

public class RegexMatch {
    public static boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;                       // empty text, empty pattern

        for (int j = 1; j <= n; j++) {         // empty text vs pattern
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];       // star matches zero copies
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);
                if (pc == '*') {
                    char before = p.charAt(j - 2);
                    boolean zero = dp[i][j - 2];               // zero copies
                    boolean more = (before == s.charAt(i - 1) || before == '.')
                                   && dp[i - 1][j];            // one more copy
                    dp[i][j] = zero || more;
                } else if (pc == '.' || pc == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];               // single match
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String text = "aab";
        String pattern = "c*a*b";
        System.out.println(isMatch(text, pattern));
    }
}

true

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    dp[0][0] = True                       # empty text matches empty pattern

    for j in range(1, n + 1):             # empty text against the pattern
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]       # star takes zero of its letter

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            pc = p[j - 1]
            if pc == '*':
                before = p[j - 2]
                zero = dp[i][j - 2]                       # star = zero copies
                more = (before == s[i - 1] or before == '.') and dp[i - 1][j]
                dp[i][j] = zero or more                   # either branch wins
            elif pc == '.' or pc == s[i - 1]:
                dp[i][j] = dp[i - 1][j - 1]               # single char match
    return dp[m][n]


text = "aab"
pattern = "c*a*b"
print(str(is_match(text, pattern)).lower())

true

function isMatch(s, p) {
  const m = s.length;
  const n = p.length;
  const dp = Array.from({ length: m + 1 }, () =>
    new Array(n + 1).fill(false)
  );

  dp[0][0] = true; // empty text matches empty pattern

  for (let j = 1; j <= n; j++) {           // empty text against pattern
    if (p[j - 1] === "*") {
      dp[0][j] = dp[0][j - 2];             // star takes zero of its letter
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const pc = p[j - 1];
      if (pc === "*") {
        const before = p[j - 2];
        const zero = dp[i][j - 2];                       // star = zero copies
        const more =
          (before === s[i - 1] || before === ".") && dp[i - 1][j]; // one more
        dp[i][j] = zero || more;
      } else if (pc === "." || pc === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];                     // single char match
      }
    }
  }
  return dp[m][n];
}

const text = "aab";
const pattern = "c*a*b";
console.log(isMatch(text, pattern));

true

Let us walk through the Python version line by line. Code first, then the why.

m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True

We grab both lengths and make a grid with one extra row and column. The extra slots hold the empty cases. We mark dp[0][0] true, because an empty text and an empty pattern do match.

for j in range(1, n + 1):
    if p[j - 1] == '*':
        dp[0][j] = dp[0][j - 2]

This handles an empty text against a non-empty pattern. The only way a pattern matches nothing is if every star chooses zero copies. So when we see a star, we look two symbols back. We skip the star and the letter before it, then borrow that earlier truth. That is why a pattern like a*b* can still match an empty text.

pc = p[j - 1]
if pc == '*':
    before = p[j - 2]
    zero = dp[i][j - 2]
    more = (before == s[i - 1] or before == '.') and dp[i - 1][j]
    dp[i][j] = zero or more

This is the star rule, the hard part. zero is the choice where the star matches no copies. We jump two symbols back with dp[i][j-2], dropping the star and its letter. more is the choice where the star matches one more copy. That is only legal when the letter before the star lines up with the current text letter, either by being equal or by being a dot. If it lines up, we eat one text letter and keep the same star, which is dp[i-1][j]. The cell is true if either choice works.

elif pc == '.' or pc == s[i - 1]:
    dp[i][j] = dp[i - 1][j - 1]

This is the plain case with no star. A dot matches any single letter, and an equal letter matches itself. Either way it is a single-character match. So we move both the text and the pattern back by one and copy that earlier answer from the diagonal.

return dp[m][n]

The bottom-right cell checked the whole text against the whole pattern. So it holds the final yes or no, which is true for this input.

⏱️ Time and Space Complexity

Plain recursion can branch on every star, so it is exponential in the worst case. Memoization solves each (i, j) position once, dropping the time to O(m × n). The bottom-up table does the same work with two loops and no recursion stack. The table needs O(m × n) memory. You can squeeze the space to O(n) by keeping only the previous row, but the full table reads more clearly in an interview.

🧩 Key Takeaways

• ✅ A dot matches any single character, and a star matches zero or more of the symbol before it.
• ✅ The cell dp[i][j] is true if the first i text letters match the first j pattern symbols.
• ✅ The star always splits into two choices: zero copies, or one more copy when the letter lines up.
• ✅ The first row handles an empty text where stars choose zero copies.
• ✅ Recursion is exponential, but the 2D table runs in O(m × n) time.

🚀 What’s Next?

• Edit Distance
• Burst Balloons