The problem
Match a string s against a pattern p in which . matches any single character and x* matches zero or more copies of the character before it. The pattern must match the whole of s, not just part of it.
Examples
- Input
s = "aa", p = "a"
- Output
false
- Input
s = "aa", p = "a*"
- Output
true
- Input
s = "ab", p = ".*"
- Output
true
Constraints
- 1 ≤ s.length ≤ 20
- 1 ≤ p.length ≤ 20
sis lowercase letters;pis lowercase letters,.and*.- Every
*follows a character it can repeat.
The idea
Let match(i, j) say whether the rest of s from i matches the rest of p from j. When p runs out, it matches only if s has too. Otherwise, first says whether s[i] exists and equals p[j] (or p[j] is .).
If p[j] is followed by *, there are two readings: use x* zero times and skip it — match(i, j + 2) — or, if first, let it eat s[i] and stay on the same pattern — match(i + 1, j). Without a *, first must hold and both move on: match(i + 1, j + 1). Filling the table from the ends back to the start means every value it needs is ready.
- Time
- O(m · n)
- Space
- O(m · n)
Solution · every language run against every case
class Solution: def isMatch(self, s: str, p: str) -> bool: m, n = len(s), len(p) # match[i][j]: does s[i:] match p[j:]? Filled from the ends back to the start. match = [[False] * (n + 1) for _ in range(m + 1)] match[m][n] = True # nothing matches nothing for i in range(m, -1, -1): for j in range(n - 1, -1, -1): first = i < m and p[j] in (s[i], ".") # does s[i] match the pattern's next letter? if j + 1 < n and p[j + 1] == "*": # "x*": use it zero times (skip it), or match one letter and stay on it match[i][j] = match[i][j + 2] or (first and match[i + 1][j]) else: match[i][j] = first and match[i + 1][j + 1] return match[0][0]