Regular Expression Matching

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[m][n] = True
    for j in range(n - 1, -1, -1):
        for i in range(m, -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]

Regular Expression Matching. Does a pattern match a whole string? A dot matches any single character. A star means zero or more of the character before it.

Take string A A, pattern A: an A is left over, so false. Pattern A star stretches over both: true. String A B, pattern dot star: true.

The naive way is plain recursion: at every star, try zero copies, or eat one character and try again. The same suffix pairs get solved over and over: exponential work.

The key idea: D P of i, j says whether the string from i matches the pattern from j. First match: character i equals pattern j, or pattern j is a dot. If a star follows, skip the pair, or, on a first match, eat one character and keep the star. Otherwise, first match, then both move on.

In code, empty matches empty. Fill from the bottom right, since each cell looks only down or right. Return D P of zero, zero.

Now string A A B, pattern C star A star B. Empty pattern: only the empty string matches. Pattern B matches only B. Pattern A star B matches B by skipping the star, A B by eating one A, A A B by eating two. C never matches, so C star is skipped, copying the next column. Top left: true.

Each of the M times N cells is constant work: order M N time and space.

Match one, skip the star, or stretch it. That's Regular Expression Matching.