regular_expression_matching
1from functools import cache 2 3 4# @leet start 5class Solution: 6 def isMatch(self, s: str, p: str) -> bool: 7 """ 8 This question asks us to create a regular expression matcher that 9 supports '.' which matches any single character, and '*', which matches 10 zero or more characters. As well, '.*' matches zero or more of every 11 character. 12 13 So, you have to handle the case of '.*' first, where you can match 14 anything up until the end of the string, so we can dfs through any 15 index until the end. 16 17 If we have a '.', we match any single character and continue, returning 18 false if s is empty. 19 20 If there's '[a-z]*', we match that character as many times as we can 21 and dfs through any of those. 22 23 At the end, we just make sure to follow the rules for '.' again since 24 it can appear as a single character. 25 """ 26 27 @cache 28 def dfs(s, p): 29 if not s and not p: 30 return True 31 32 if len(p) > 1: 33 curr, after = p[:2] 34 if curr == ".": 35 if after == "*": 36 return any(dfs(s[i:], p[2:]) for i in range(len(s) + 1)) 37 if not s: 38 return False 39 return dfs(s[1:], p[1:]) 40 if after == "*": 41 i = 0 42 while i < len(s) and s[i] == curr: 43 i += 1 44 return any(dfs(s[x:], p[2:]) for x in range(i + 1)) 45 46 if not p: 47 return not s 48 if not s: 49 return not p 50 51 if p[0] == "." or s[0] == p[0]: 52 return dfs(s[1:], p[1:]) 53 54 return False 55 56 return dfs(s, p) 57 58 59# @leet end 60 61 62def test(): 63 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def isMatch(self, s: str, p: str) -> bool: 8 """ 9 This question asks us to create a regular expression matcher that 10 supports '.' which matches any single character, and '*', which matches 11 zero or more characters. As well, '.*' matches zero or more of every 12 character. 13 14 So, you have to handle the case of '.*' first, where you can match 15 anything up until the end of the string, so we can dfs through any 16 index until the end. 17 18 If we have a '.', we match any single character and continue, returning 19 false if s is empty. 20 21 If there's '[a-z]*', we match that character as many times as we can 22 and dfs through any of those. 23 24 At the end, we just make sure to follow the rules for '.' again since 25 it can appear as a single character. 26 """ 27 28 @cache 29 def dfs(s, p): 30 if not s and not p: 31 return True 32 33 if len(p) > 1: 34 curr, after = p[:2] 35 if curr == ".": 36 if after == "*": 37 return any(dfs(s[i:], p[2:]) for i in range(len(s) + 1)) 38 if not s: 39 return False 40 return dfs(s[1:], p[1:]) 41 if after == "*": 42 i = 0 43 while i < len(s) and s[i] == curr: 44 i += 1 45 return any(dfs(s[x:], p[2:]) for x in range(i + 1)) 46 47 if not p: 48 return not s 49 if not s: 50 return not p 51 52 if p[0] == "." or s[0] == p[0]: 53 return dfs(s[1:], p[1:]) 54 55 return False 56 57 return dfs(s, p)
def
isMatch(self, s: str, p: str) -> bool:
7 def isMatch(self, s: str, p: str) -> bool: 8 """ 9 This question asks us to create a regular expression matcher that 10 supports '.' which matches any single character, and '*', which matches 11 zero or more characters. As well, '.*' matches zero or more of every 12 character. 13 14 So, you have to handle the case of '.*' first, where you can match 15 anything up until the end of the string, so we can dfs through any 16 index until the end. 17 18 If we have a '.', we match any single character and continue, returning 19 false if s is empty. 20 21 If there's '[a-z]*', we match that character as many times as we can 22 and dfs through any of those. 23 24 At the end, we just make sure to follow the rules for '.' again since 25 it can appear as a single character. 26 """ 27 28 @cache 29 def dfs(s, p): 30 if not s and not p: 31 return True 32 33 if len(p) > 1: 34 curr, after = p[:2] 35 if curr == ".": 36 if after == "*": 37 return any(dfs(s[i:], p[2:]) for i in range(len(s) + 1)) 38 if not s: 39 return False 40 return dfs(s[1:], p[1:]) 41 if after == "*": 42 i = 0 43 while i < len(s) and s[i] == curr: 44 i += 1 45 return any(dfs(s[x:], p[2:]) for x in range(i + 1)) 46 47 if not p: 48 return not s 49 if not s: 50 return not p 51 52 if p[0] == "." or s[0] == p[0]: 53 return dfs(s[1:], p[1:]) 54 55 return False 56 57 return dfs(s, p)
This question asks us to create a regular expression matcher that supports '.' which matches any single character, and '', which matches zero or more characters. As well, '.' matches zero or more of every character.
So, you have to handle the case of '.*' first, where you can match anything up until the end of the string, so we can dfs through any index until the end.
If we have a '.', we match any single character and continue, returning false if s is empty.
If there's '[a-z]*', we match that character as many times as we can and dfs through any of those.
At the end, we just make sure to follow the rules for '.' again since it can appear as a single character.
def
test():