Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution(object):
- def isMatch(self, s, p):
- """
- :type s: str
- :type p: str
- :rtype: bool
- """
- # Create a 2D DP table to store the matching results
- dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
- # Base case: an empty pattern matches an empty string
- dp[0][0] = True
- # Handling cases where '*' can match zero characters
- for j in range(1, len(p) + 1):
- if p[j - 1] == '*':
- dp[0][j] = dp[0][j - 2]
- # Dynamic Programming
- for i in range(1, len(s) + 1):
- for j in range(1, len(p) + 1):
- if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
- dp[i][j] = dp[i - 1][j - 1]
- elif p[j - 1] == '*':
- dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))
- else:
- dp[i][j] = False
- return dp[len(s)][len(p)]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement