Regular Expression Matching

Hard

The problem

Return true if the pattern p matches the whole string s. In p, "." matches any single character, and "*" means the character just before it can appear zero or more times (so "a*" matches "", "a", "aa", ...). A "*" always follows a character or a ".".

Example 1
Input: s = "aa", p = "a"
Output: false
The pattern covers one character but s has two.
Example 2
Input: s = "aa", p = "a*"
Output: true
"a*" can stand for two "a" characters.
Example 3
Input: s = "ab", p = ".*"
Output: true
".*" can stand for any characters.
Example 4
Input: s = "mississippi", p = "mis*is*p*."
Output: false
The pattern can match "mississi" (m, i, ss, i, ss, nothing for p*, then "." takes an i), but "ppi" is left over in s.

Limits

0 ≤ len(s) ≤ 20, 1 ≤ len(p) ≤ 20
s has only lowercase letters
p has only lowercase letters, "." and "*"
Every "*" has a valid character before it

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A "*" applies to the character before it: zero copies, or one more copy.

The idea

dp[i][j] over prefixes. If p[j−1] is "*": zero copies dp[i][j−2], or (s[i−1] matches p[j−2]) and dp[i−1][j]. Otherwise characters (or ".") must match and dp[i−1][j−1] must hold.

Target: O(m·n) time

Go function shape

func isMatch(s string, p string) bool

Reference solution

Tested with go test. Try it yourself first, then compare.

// IsMatch: regular expression matching with '.' and '*'.
// dp[i][j] = the first i characters of s match the first j characters of p.
func IsMatch(s, p string) bool {
	dp := make([][]bool, len(s)+1)
	for i := range dp {
		dp[i] = make([]bool, len(p)+1)
	}
	dp[0][0] = true
	for j := 2; j <= len(p); j++ {
		if p[j-1] == '*' {
			dp[0][j] = dp[0][j-2] // "a*" can match the empty string
		}
	}
	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(p); j++ {
			if p[j-1] == '*' {
				dp[i][j] = dp[i][j-2] // zero copies of the starred letter
				if p[j-2] == '.' || p[j-2] == s[i-1] {
					dp[i][j] = dp[i][j] || dp[i-1][j] // one more copy
				}
			} else if p[j-1] == '.' || p[j-1] == s[i-1] {
				dp[i][j] = dp[i-1][j-1]
			}
		}
	}
	return dp[len(s)][len(p)]
}

Read the lesson: 2-D Dynamic Programming