Description
Decide whether the entire string s matches pattern p. A dot matches any one character; a star repeats its preceding character or dot zero or more times. Assume each star has a valid preceding token.
Solution
def is_match(s, p):
rows, cols = len(s), len(p)
dp = [[False] * (cols + 1) for _ in range(rows + 1)]
dp[0][0] = True
for j in range(2, cols + 1):
if p[j - 1] == "*":
dp[0][j] = dp[0][j - 2]
for i in range(1, rows + 1):
for j in range(1, cols + 1):
if p[j - 1] == "*":
matches = p[j - 2] == "." or p[j - 2] == s[i - 1]
dp[i][j] = dp[i][j - 2] or (matches and dp[i - 1][j])
elif p[j - 1] == "." or p[j - 1] == s[i - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[rows][cols]Examples
Example 1
- Input
["aa","a"]- Output
false
A single a cannot cover two characters.
Example 2
- Input
["aa","a*"]- Output
true
Repeat a twice.
Example 3
- Input
["ab",".*"]- Output
true
Dot-star can consume both characters.
Approach
Build a prefix DP table. A plain matching token consumes one character from each prefix. A starred token either disappears with its preceding token, or consumes one matching input character while retaining the same pattern prefix.
Time & space
O(mn + m + n) time and O(mn + m + n) auxiliary space, where m and n are string and pattern lengths.