Regular Expression Matching

Problem in Plain English

Given a string and a pattern with dot and star operators, decide whether the whole string matches the whole pattern. A dot matches any single character and a star repeats its preceding element zero or more times.

Problem Statement

Given lowercase string s and valid pattern p, return whether the entire string matches the entire pattern. A literal letter matches itself, . matches exactly one character, and * repeats the immediately preceding letter or dot zero or more times. For example, a* can match an empty remainder, one a, or several consecutive a characters.

This is the restricted dot-and-star language: * is not a standalone wildcard, and there are no alternation, grouping, or other operators. Return a boolean; a matching substring alone is insufficient. Example 1 has s = "aa" and p = "a*", so two repetitions cover both characters and return true.

Constraints

1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters.
p contains only lowercase English letters, . and *.
Every * has a valid preceding character to repeat.

Examples

Example 1

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

Use a* twice: the first a consumes one repetition and the second consumes another. Then stop repeating. Both string and pattern are exhausted, so the full match is true.

Example 2

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

The single literal a consumes only the first character. A second a remains after the pattern ends, so a prefix match does not count and the answer is false.

Example 3

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

Repeat the dot twice. Its first use matches a and its second matches b; each dot use consumes exactly one character. Stopping afterward covers the whole string and returns true.

Example 4

Input: s = "aab", p = "c*a*b"
Output: true

Use zero copies of c, two copies of a, and then the literal b. The initial c* disappears completely; requiring at least one copy would wrongly reject this valid full match.

Intuition

A star makes the repetition count uncertain: in Example 1, a* could take zero, one, or two copies, but only two cover all of "aa". Resolve that uncertainty with two exhaustive choices: skip the whole atom-star pair, or consume one matching character and leave that pair available. Ordinary letters and dots consume exactly one character. Different repetition choices can reach the same pair of positions; a table stores each pair once instead of exploring its continuations again.

Approaches

Brute Force Recursion

Solution Details

Reveal Brute Force Recursion: intuition, complexity, and code

Intuition

Explore every possible repetition count using suffix positions match(i, j): does s[i:] match p[j:]? A plain letter or dot consumes one character from each side. For an atom followed by *, try zero copies by advancing j by two; if that fails and the current character matches, consume one character while keeping j fixed. This reveals the repeated suffix work that the table removes.

Step-by-Step Logic

Define match(i, j) for the two remaining suffixes, and start at (0, 0). When j reaches the pattern length, return whether i also reaches the string length.
Otherwise compute first: a character must remain, and it must equal the current pattern atom or be covered by a dot. In Example 1, first is true at (0, 0) and p[1] is a star.
For an atom followed by a star, first skip both pattern characters. From (0, 0), (0, 2) fails because "aa" remains after the pattern ends.
If skipping failed and first is true, consume one string character while leaving the atom-star pair in place. (1, 0) first tries (1, 2), which fails because one a remains, and then tries (2, 0).
At (2, 0), no string character remains, so first is false. Skipping a* reaches (2, 2), where both suffixes are empty and the answer is true. No consume call is made from this state.
Return that true result through (2, 0), (1, 0), and (0, 0). For a non-star atom, require first and advance both indices by one instead.

Why It Works

Induct on the number of remaining string and pattern positions. If the pattern is exhausted, a full match exists exactly when the string is exhausted too. For a plain atom, any match must consume one compatible character and then match both remaining suffixes. For an atom-star pair, every valid match either uses zero copies, covered by match(i, j + 2), or uses at least one compatible character, covered by match(i + 1, j) with the remaining copies still available. Both branches construct only legal matches and together cover every repetition count. Each recursive call advances at least one index, so the induction terminates; short-circuiting after a true branch cannot change the boolean result.

Dry Run

Brute Force Recursion: variable states at each step
Event	State `(i, j)`	Remaining string / pattern	`first`	Branch or return
enter root	`(0, 0)`	`aa` / `a*`	true	try zero copies at `(0, 2)`
base case	`(0, 2)`	`aa` / empty	not evaluated	false: string remains
consume from root	`(1, 0)`	`a` / `a*`	true	try zero copies at `(1, 2)`
base case	`(1, 2)`	`a` / empty	not evaluated	false: string remains
consume again	`(2, 0)`	empty / `a*`	false	try zero copies at `(2, 2)`
base case	`(2, 2)`	empty / empty	not evaluated	true: both exhausted
return to parent	`(2, 0)`	empty / `a*`	false	skip is true; consume branch is not evaluated
return to parent	`(1, 0)`	`a` / `a*`	true	skip false; consume true; return true
return root	`(0, 0)`	`aa` / `a*`	true	skip false; consume true; final answer true

Complexity Analysis

Time Complexity

O(2^{m+n})

Space Complexity

O(m+n)

Let m = s.length and n = p.length. Each call has at most two children, and every child increases i or j, so a path has at most m + n + 1 frames. A binary tree of that depth gives the stated safe upper bound, not a tight count for every input; ambiguous repeated atoms with a late mismatch can explore exponentially many paths. There is no memoization. Each frame holds only indices and booleans, and the code passes the original immutable strings without slicing, so peak extra space is O(m + n), not the total number of calls. The published maximum lengths keep recursion depth small even when total branching is expensive.

Code

Solution.java

1class Solution {2    public boolean isMatch(String s, String p) {3        return match(s, p, 0, 0);4    }5
6    private boolean match(String s, String p, int i, int j) {7        // Exhausting the pattern is success only when the whole string is consumed.8        if (j == p.length()) {9            return i == s.length();10        }11        boolean first = i < s.length()12                && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');13        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {14            // Skip the entire atom-star pair, or consume one character and keep the pair.15            return match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));16        }17        return first && match(s, p, i + 1, j + 1);18    }19}

Hints

Hint 1

A matching prefix is insufficient: what must be true when the pattern ends?

Hint 2

For an atom followed by a star, separate zero copies from at least one copy. After taking one copy, why should the same atom-star pair remain available?

Hint 3

Use a pair of indices as the state. For the table, let prefix lengths include zero; a star reads two columns left and, for a matching character, one row above.

Edge Cases

s = "a", p = "ab*" is true: the final b* uses zero copies after the literal a consumes the string.
s = "b", p = "a*b" is true even though the first atom does not match; the zero-copy branch must remain available.
s = "a", p = "." is true, but s = "ab", p = "." is false: a dot consumes exactly one character.
s = "ab", p = ".*c" is false: the final literal c cannot disappear. Greedily consuming the whole string with .* does not finish the pattern.
s = "aaa", p = "a*a" is true: leave one a for the final literal rather than committing greedily to a repetition count.
Although published inputs are nonempty, recursion reaches empty suffixes and the table needs an empty-prefix row. Defensive calls with s = "", p = "a*b*" return true; with s = "a", p = "" they return false.

Common Mistakes and Interview Tips

Treating * as the glob wildcard that matches arbitrary characters. Here it repeats only its preceding atom, which may itself be a dot.
Consuming one star repetition and then advancing past the pair prevents further repetitions. Recursion keeps j fixed; the table reads above in the same column.
Allowing a star to consume without checking the preceding atom matches, or requiring at least one copy and losing the zero-copy branch.
Returning true as soon as one side ends. Remaining starred pairs may disappear, but remaining literal atoms or string characters cannot.
Skipping the empty-string initialization, or copying one column left for zero repetitions instead of removing both atom and star.
Aliasing all Python or JavaScript table rows: a write to one row then corrupts other prefix states. Allocate each row independently.
Interview tip: explain both star predecessors and their meanings before writing the recurrence. The uncached recursion has small depth but can still branch exponentially on a late mismatch; the table has only one state per prefix pair.

Key Takeaway

When an operator can use zero copies or consume another character without moving past itself, separate those cases explicitly. Recording both string and pattern positions turns repeated matching paths into a finite table of shared states.