Problem statement

Implement regular-expression matching over the entire input string with support for:

• . — matches any single character
• * — matches zero or more of the preceding element

Given s and pattern p, return true when p matches all of s.

Example 1

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

Example 2

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

Example 3

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means zero or more of any character.

Constraints

• 0 <= s.length <= 12
• 1 <= p.length <= 12
• s has lowercase letters; p has lowercase letters, '.' and '*'.
• '*' is always preceded by a valid element.

Hints for Regular Expression Matching

1. Hint 1

   dp[i][j]: does p[0..j) match s[0..i)?

2. Hint 2

   For 'x*': either use it zero times (dp[i][j-2]) or consume one matching char (dp[i-1][j]).

How to solve Regular Expression Matching

Let dp[i][j] mean "the first j characters of the pattern match the first i characters of the string". Ordinary characters and . advance both by one. A * is the interesting case: it governs the element before it, and can be used zero times (skip both the element and the star) or one more time (consume one string character and keep the star available).

Approach

1. dp[0][0] = true — an empty pattern matches an empty string.
2. Seed the first row: a pattern can match the empty string only through x* groups, so dp[0][j] = dp[0][j-2] when p[j-1] is *.
3. For a normal character or ., dp[i][j] = dp[i-1][j-1] provided the characters match.
4. For *, start with dp[i][j] = dp[i][j-2] (zero occurrences).
5. If the starred element also matches s[i-1], additionally allow dp[i-1][j] — consuming one character and keeping the star.

Why it works

Splitting on how the pattern's last element is used covers every possibility exactly once: a plain element must consume exactly one character, and a starred element consumes zero or extends a match that already used it. The dp[i-1][j] term is the crucial one — keeping j fixed is what lets a single * absorb arbitrarily many characters without enumerating how many. The empty-string row must be seeded separately because x* can vanish, and nothing else can.

Complexity

• Time — O(|s| · |p|)
• Space — O(|s| · |p|)

Pitfalls

• A * binds to the element before it, so skipping the group means stepping back two pattern positions, not one.
• The first row needs its own pass; without it, patterns like "a*b*" fail to match the empty string.
• When extending a star, keep j unchanged and decrease i — swapping those is the classic error.
• . matches any single character, including in the starred-element comparison, so ".*" matches everything.

Reference solution

Python

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

Java

public static boolean isMatch(String s, String p) {
    int n = s.length(), m = p.length();
    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[0][0] = true;
    for (int j = 1; j <= m; j++) {
        if (p.charAt(j - 1) == '*' && j >= 2) dp[0][j] = dp[0][j - 2];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char pc = p.charAt(j - 1);
            if (pc == '*') {
                if (j >= 2) {
                    dp[i][j] = dp[i][j - 2];
                    char prev = p.charAt(j - 2);
                    if ((prev == '.' || prev == s.charAt(i - 1)) && dp[i - 1][j]) dp[i][j] = true;
                }
            } else if (pc == '.' || pc == s.charAt(i - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[n][m];
}

C++

bool isMatch(string s, string p) {
    int n = (int) s.size(), m = (int) p.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
    dp[0][0] = true;
    for (int j = 1; j <= m; j++) {
        if (p[j - 1] == '*' && j >= 2) dp[0][j] = dp[0][j - 2];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char pc = p[j - 1];
            if (pc == '*') {
                if (j >= 2) {
                    dp[i][j] = dp[i][j - 2];
                    char prev = p[j - 2];
                    if ((prev == '.' || prev == s[i - 1]) && dp[i - 1][j]) dp[i][j] = true;
                }
            } else if (pc == '.' || pc == s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[n][m];
}

JavaScript

var isMatch = function(s, p) {
    const n = s.length, m = p.length;
    const dp = [];
    for (let i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= m; j++) {
        if (p[j - 1] === "*") dp[0][j] = dp[0][j - 2];
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (p[j - 1] === "*") {
                dp[i][j] = dp[i][j - 2] || ((p[j - 2] === "." || p[j - 2] === s[i - 1]) && dp[i - 1][j]);
            } else {
                dp[i][j] = (p[j - 1] === "." || p[j - 1] === s[i - 1]) && dp[i - 1][j - 1];
            }
        }
    }
    return dp[n][m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Prefix and Suffix Search Hard
• Recover a Tree From Preorder Traversal Hard
• Minimum Time to Revert Word to Initial State II Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• K-Similar Strings Hard