Course4all

Regular Expression Matching

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Backtracking.

Regular Expression Matching

The Matching Logic

Implement regular expression matching with support for '.' and '*'.
  • '.' matches any single character.
  • '*' matches zero or more of the preceding element.

The Star (*) Dilemma

The '' is the most complex part of this problem. When we encounter a '', we have two choices:
  1. Zero match: Skip the preceding element and the '*' (e.g., a* matches empty string).
  2. One or more match: If the current character matches the preceding element, we consume one character of the string and stay at the same position in the pattern to potentially match more.
Implement regex matching with support for '.' and '*'. Includes visual state-space analysis.
Hard

Examples

Input: s = "aa", p = "a*"
Output: true
Input: s = "mississippi", p = "mis*is*p*."
Output: false
Approach 1

Level I: Recursive Backtracking (Naive)

Intuition

Handle the base match, then branch for the '*' character.
For each call, check if the first character matches. If the second character of the pattern is '*', branch into 'skip' or 'consume' cases.
⏱ O((S+P) * 2^{S+P/2})💾 O(S^2 + P^2)

Detailed Dry Run

s="aa", p="a*" | Step | s | p | First Match? | Action | | :--- | :--- | :--- | :--- | :--- | | 1 | "aa" | "a*" | YES | '*' detected, split | | 2.1 | "aa" | "" | NO | Skip branch FAIL | | 2.2 | "a" | "a*" | YES | Consume branch, recurse | | 3.1 | "" | "a*" | YES | Consume branch, RES: true |
java
class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        boolean firstMatch = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));

        if (p.length() >= 2 && p.charAt(1) == '*') {
            return (isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p)));
        } else {
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
    }
}
Approach 2

Level II: Top-Down Memoization

Intuition

Cache results of (i, j) pairs where i is index in s and j is index in p.
The naive recursion has overlapping subproblems. By storing results in a 2D array/hashmap, we reduce complexity to O(SimesP)O(S imes P).
⏱ O(S * P)💾 O(S * P)

Detailed Dry Run

Cache entries for s="aa", p="a*": (0, 0) -> calls (0, 2) and (1, 0) (0, 2) -> true (base case) (1, 0) -> calls (1, 2) and (2, 0) ... all stored in memo table.
java
class Solution {
    public boolean isMatch(String s, String p) {
        Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
        return dp(0, 0, s, p, memo);
    }
    private boolean dp(int i, int j, String s, String p, Boolean[][] memo) {
        if (memo[i][j] != null) return memo[i][j];
        boolean res;
        if (j == p.length()) {
            res = i == s.length();
        } else {
            boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                res = dp(i, j + 2, s, p, memo) || (first && dp(i + 1, j, s, p, memo));
            } else {
                res = first && dp(i + 1, j + 1, s, p, memo);
            }
        }
        return memo[i][j] = res;
    }
}
Approach 3

Level III: Bottom-Up Dynamic Programming

Intuition

Build a table dp[i][j] where dp[i][j] is true if s[i:] matches p[j:].
Initialize dp[len(s)][len(p)] = true. Fill the table backwards from the base case.
⏱ O(S * P)💾 O(S * P)

Detailed Dry Run

DP Table for s="aa", p="a*": | | a | * | (end) | |---|---|---|-------| | a | T | T | F | | a | T | T | F | |(e)| F | T | T |
java
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[m][n] = true;

        for (int i = m; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                boolean first = i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
                if (j + 1 < n && p.charAt(j + 1) == '*') {
                    dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
                } else {
                    dp[i][j] = first && dp[i + 1][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionN-Queens II
Next Question →Wildcard Matching