Regular Expression Matching

Master this topic with zero to advance depth.

Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for . and * where:

. Matches any single character.
* Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Visual Representation

s = "aa", p = "a*"

- 'a*' can match "", "a", "aa", "aaa", etc.
- Since it matches "aa", result is True.

s = "ab", p = ".*"
- '.*' matches anything. Result is True.

Hard

Examples

Input: s = "aa", p = "a"
Output: false
index 0 matches 'a', but index 1 does not. Pattern is exhausted.

Input: s = "aa", p = "a*"
Output: true

Input: s = "ab", p = ".*"
Output: true

Approach 1

Level I: Brute Force (Recursion)

Intuition

At each step, we check if the first character of the string matches the first character of the pattern. Special handling is needed for '*' which can match zero or more of the preceding element.

Thought Process

If p is empty, return true if s is also empty.
Check if the first characters match (s[0] == p[0] or p[0] == '.').
If p[1] == '*':
- Either skip '*' and preceding char (zero match): isMatch(s, p[2:]).
- Or if first chars match, consume one char of s and keep pattern: first_match && isMatch(s[1:], p).
Else: If first chars match, recurse on isMatch(s[1:], p[1:]).

⏱ Exponential💾 O(N+M) for recursion stack

Detailed Dry Run

s = "aa", p = "a*"

p[1] is '*'. Try skip: isMatch("aa", "") -> False.
Try consume: 'a'=='a', so isMatch("a", "a*").
Again '', try consume: 'a'=='a', so isMatch("", "a").
Again '*', try skip: isMatch("", "") -> True.

java

public class Main {
    public static 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));
        }
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a*")); // true
    }
}

Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The recursive regex matching recalculates many overlapping (i, j) states. Adding a 2D memo array indexed by (si, pi) eliminates repeated work.

Visual

s="aa", p="a*"
solve(0,0): p[1]='*' -> zero match: solve(0,2); one+ match: solve(1,0)
solve(1,0): cached after first call!

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s="aa", p="a*". memo[0][0]: p[1]='*', try zero: memo[0][2]=T (empty matches empty). Return True.

java

import java.util.*;

public class Main {
    static Integer[][] memo;
    static String s, p;
    public static int solve(int si, int pi) {
        if (pi == p.length()) return si == s.length() ? 1 : 0;
        if (memo[si][pi] != null) return memo[si][pi];
        boolean firstMatch = si < s.length() && (p.charAt(pi) == s.charAt(si) || p.charAt(pi) == '.');
        int res;
        if (pi + 1 < p.length() && p.charAt(pi + 1) == '*') {
            res = (solve(si, pi + 2) == 1 || (firstMatch && solve(si + 1, pi) == 1)) ? 1 : 0;
        } else {
            res = (firstMatch && solve(si + 1, pi + 1) == 1) ? 1 : 0;
        }
        return memo[si][pi] = res;
    }

    public static boolean isMatch(String str, String pattern) {
        s = str; p = pattern;
        memo = new Integer[s.length() + 1][p.length() + 1];
        return solve(0, 0) == 1;
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a*")); // true
    }
}

⚠️ Common Pitfalls & Tips

The '*' operator makes regex DP tricky. Always first try the 'zero match' path (pi+2), then only try 'one+ match' if firstMatch is true to avoid infinite loops.

Approach 3

Level III: Dynamic Programming (Bottom-Up 2D)

Intuition

We use a 2D table dp[i][j] to represent if s[0...i-1] matches p[0...j-1].

Thought Process

dp[0][0] = true (empty string matches empty pattern).
Pattern with '*':
- Case 1: '*' matches zero characters: dp[i][j] = dp[i][j-2].
- Case 2: '*' matches one or more: dp[i][j] = dp[i-1][j] if s[i-1] matches p[j-2].
Pattern without '*':
- If s[i-1] matches p[j-1] (either same char or '.'), dp[i][j] = dp[i-1][j-1].

⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

s = "aa", p = "a*"

i\j	""	'a'	'*'
""	T	F	T (zero 'a')
'a'	F	T	T (one 'a')
'a'	F	F	T (two 'a')

java

public class Main {
    public static boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for (int j = 2; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[s.length()][p.length()];
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a*")); // true
    }
}

⚠️ Common Pitfalls & Tips

Handling the empty string base case for patterns like a*b*c* is tricky. Ensure you initialize dp[0][j] correctly for '*' characters.

← Previous QuestionClimbing Stairs

Next Question →Burst Balloons

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.