Regular Expression Matching

Hard25–30 min

Topics

Dynamic ProgrammingString

Companies

GoogleFacebookMicrosoft

A pattern built from ordinary letters, a single-character wildcard (.), and a repeat marker (*) is checked against a target string for a full match, not a partial one. The tricky part is that * doesn't stand alone — it always modifies whatever came right before it, meaning that character (or .) can appear zero times, once, or many times in a row. A naive check has to be willing to try every repeat count a * pair could possibly use before it knows whether the whole match works out. The way through is the same idea used for matching without repeats: build up an answer to "can this much of the pattern explain this much of the string" one small piece at a time. A * pair offers two independent paths to a yes — skip it completely, or use it once and lean on a smaller version of the same question. Filling in that grid systematically, from the empty prefixes outward, sidesteps the need to ever guess how many repetitions to try.

Test Case 1:

Input:s = "aa", p = "a"

Output:false

Explanation:p has no wildcard, so it must match letter-for-letter — "a" is one character short of "aa".

Test Case 2:

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

Output:true

Explanation:'*' means zero or more of the character right before it — here that's 'a', so "a*" can stretch to cover both a's.

Test Case 3:

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

Output:true

Explanation:'.' matches any single character, and '*' lets it repeat any number of times, so ".*" covers the whole string.

Constraints

◆0 ≤ s.length ≤ 10
◆0 ≤ p.length ≤ 10
◆s consists of lowercase English letters only
◆p consists of lowercase English letters, '.', and '*'
◆It is guaranteed that for each appearance of '*', there is a previous valid character to match

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Look only at the first characters of what's left of s and p. If the character right after the current pattern position is '*', that pair (character + '*') can either be dropped entirely — matching zero occurrences and moving on in the pattern only — or, if the current pattern character actually matches the current string character, one occurrence can be consumed from s while staying on the same pattern position to consider repeating it again. Without a following '*', the current characters must match outright and both strings shrink together. The problem keeps reducing to a smaller version of itself until either string runs out, but the same (s, p) pair can be reached via different repeat counts, so a lot of the work repeats.

TimeO(2ⁿ⁺ᵐ)

SpaceO(n+m)

Java

Try it out

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) return s.isEmpty();
        boolean firstMatch = !s.isEmpty() && (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0));
        if (p.length() >= 2 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
        }
        return firstMatch && isMatch(s.substring(1), p.substring(1));
    }
}

Optimal — Bottom-Up DP

Optimal

Track, for every prefix of s and every prefix of p, whether that prefix of p can fully explain that prefix of s. When the current pattern character is followed by '*', that pair contributes in one of two ways — either it's skipped altogether, so the answer copies straight from two columns back on the same row, or, if the character right before the '*' actually matches the current character of s, one repetition is peeled off and the answer copies from the row above on the same column. Without a '*', a plain letter or '.' just needs the previous prefixes to already agree, diagonally. The first row gets special treatment up front, since only patterns built entirely from "x*" pairs can ever match an empty s.

TimeO(n*m)

SpaceO(n*m)