题解 | #正则表达式匹配#
正则表达式匹配
https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
class Solution:
def match(self , str: str, pattern: str) -> bool:
if not pattern:
return not str
firstMatch = str and pattern[0] in {str[0], '.'}
if len(pattern) >= 2 and pattern[1] == '*':
return (self.match(str, pattern[2:]) or firstMatch and self.match(str[1:], pattern))
else:
return firstMatch and self.match(str[1:], pattern[1:])
解题思路
本题采用的是递归的思想。
- 如果pattern不存在的话，就返回not str（当str不存在时，二者可以匹配上，返回True；都则返回False）。
- 给firstMatch赋值，如果str还有，并且pattern[0]==str[0]或者是等于'.'，则为True；否则为False。
- 如果当前pattern长度大于等于2，并且pattern[1]等于'*'，则返回（pattern[2:]后的匹配结果）或（firstMatch and str[1:]后的匹配结果）；否则的话，返回firstMatch and （str[1:]，pattern[1:]后的匹配结果）。
复杂度
- 时间复杂度和空间复杂度都为O（mn）。
