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
- """
- m, n = len(s), len(p)
- dp = [[False] * (n + 1) for _ in range(m + 1)]
- dp[0][0] = True # Empty string matches empty pattern
- for i in range(1, m + 1):
- for j in range(1, n + 1):
- if p[j - 1] == '.':
- dp[i][j] = dp[i - 1][j - 1]
- elif p[j - 1] == s[i - 1]:
- dp[i][j] = dp[i - 1][j - 1]
- elif p[j - 1] == '*':
- # Try matching zero or more of the preceding element
- # 1. Match zero times (skip '*')
- dp[i][j] = dp[i][j - 1]
- # 2. Match one or more times (match current char and try remaining pattern)
- for k in range(i):
- if dp[k][j - 1] and (p[j - 2] == '.' or p[j - 2] == s[k - 1]):
- dp[i][j] = True
- break # Optimization: stop after finding a match
- return dp[m][n]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement