Course4all
Join us on telegram
Home/dsa/Backtracking/Regular Expression Matching

Regular Expression Matching

Master this topic with zero to advance depth.

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];
    }
}
← Previous QuestionN-Queens II
Next Question →Wildcard Matching