Created
October 8, 2021 16:34
-
-
Save ssshukla26/81d20d42d788542764fe0bcaa0913ceb to your computer and use it in GitHub Desktop.
RegEx Matching Leetcode 10
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Leetcode : https://leetcode.com/problems/regular-expression-matching/ | |
| # Reference : https://www.youtube.com/watch?v=HAA8mgxlov8 | |
| from functools import cache | |
| class Solution: | |
| def isMatch(self, s: str, p: str) -> bool: | |
| a = len(s) | |
| b = len(p) | |
| @cache | |
| def matches(n: int = 0, m: int = 0) -> bool: | |
| # Check if pattern is exhausted, then return | |
| # True or False checking if the string is exahusted | |
| if m >= b: | |
| return n >= a | |
| # Match the current character, only if in bounds | |
| is_matched = (n < a) and (s[n] == p[m] or p[m] == ".") | |
| # check if the next character in pattern is "*" | |
| if m+1 < b and p[m+1] == "*": | |
| # Decision Tree: either move two steps in pattern or | |
| # stay at the same poistion and move one step in target string. | |
| return matches(n, m+2) or (is_matched and matches(n+1, m)) | |
| else: | |
| # Check if current character is matched, if yes, | |
| # then move to next step in both pattern and string | |
| return is_matched and matches(n+1, m+1) | |
| return matches() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment