805. Pattern Matcher
A log filter describes the lines it wants with a pattern p made of lowercase letters, dots and stars. A letter matches only itself, a . matches any single character, and a * applies to the element right before it (a letter or a dot), allowing that element to occur zero or more times in a row. A * that is the first symbol of p, or that directly follows another *, has nothing to repeat and is simply ignored.
Given a line s, return true if the pattern matches the whole line, otherwise false.
Aim for O(n*m) time, where n and m are the lengths of s and p, and O(m) extra space.
Example 1
- Input:
- s = "toottoo", p = "t.o*t*o"
- Output:
- false
- Explanation:
The pattern "t.o*t*o" does not match the whole string "toottoo".
Example 2
- Input:
- s = "kayakkk", p = "ka*y.k*"
- Output:
- true
- Explanation:
The pattern "ka*y.k*" matches the whole string "kayakkk".
Example 3
- Input:
- s = "ssamba", p = "s*a.b*a*"
- Output:
- true
- Explanation:
The pattern "s*a.b*a*" matches the whole string "ssamba".
Constraints
1 ≤ s.length, p.length ≤ 1000
s contains only lowercase letters; p contains lowercase letters, . and *.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n*m)
- Space
- O(m)