Regular Expression Matching

HardDynamic Programming (1-D & 2-D)NeetCode 150SeniorOpen on LeetCodeUpdated Nov 11, 2026

You're given a string s and a pattern p. The pattern uses lowercase letters plus two special characters: '.' matches any single character, and '*' matches zero or more copies of the character just before it. Return true if the pattern matches all of s, from the first character to the last.

Examples

s = "xyy", p = "xy*" returns true

y* matches the two ys.

s = "ab", p = ".*c" returns false

.* can match ab, but the pattern still needs a c at the end, and s has none.

s = "", p = "z*" returns true

z* can match zero zs, which covers the empty string.

Constraints

1 <= s.length <= 20
1 <= p.length <= 20
s contains only lowercase English letters.
p contains only lowercase English letters, '.', and '*'.
Every '*' in p follows a valid character.

Hints

Hint 1

A '*' changes how the character before it behaves. When you look at p[j], what else do you need to look at?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Let dp[i][j] be true when s[i:] matches p[j:]. dp[len(s)][len(p)] is true, since two empty suffixes match. Fill the table from the end. Let first mean i is in range and p[j] is s[i] or '.'. If p[j + 1] is '*', the pair either matches nothing, giving dp[i][j + 2], or eats one character and stays on the same pattern position, giving first and dp[i + 1][j]. Otherwise dp[i][j] = first and dp[i + 1][j + 1]. Row i = len(s) matters too: it is how a pattern like z* matches an empty suffix. O(m * n) time and space.

Time

O(m * n)

Space

O(m * n)

Pitfall

Treating '*' as a wildcard by itself. It always binds to the character before it, so look ahead to p[j + 1] when deciding how to handle p[j], and skip both characters for the zero-copy case.

Solutions

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) == '.' || p.charAt(j) == s.charAt(i));
                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];
    }
}

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[m][n] = True
        for i in range(m, -1, -1):
            for j in range(n - 1, -1, -1):
                first = i < m and p[j] in (s[i], ".")
                if j + 1 < n and p[j + 1] == "*":
                    dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j])
                else:
                    dp[i][j] = first and dp[i + 1][j + 1]
        return dp[0][0]