#10

Regular Expression Matching

international master · 1980 · lc hard +32 · verified · 30.5% accepted · 13,262 likes · top 8%

⚑ String Matching DP (LCS / Edit Distance)

Description

Implement pattern matching for string s and pattern p where '.' matches any single character and '*' matches zero or more of the preceding element. The entire input string must be matched, not just a prefix.

Example 1:

Input: s = "aa", p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"

Output: true

Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"

Output: true

Explanation: ".*" means "zero or more (*) of any character (.)".

Code

1

2

3

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

class Solution:
    def isMatch(self, s: str, p: str) -> bool: