Leetcode 44. Wildcard Matching

Seawolf

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

1. class Solution:
   
2.     def isMatch(self, s: str, p: str) -> bool:
   
3.         m, n = len(s), len(p)
   
4.         dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]
   
5.         
   
6.         for i in range(m + 1):
   
7.             for j in range(n + 1):
   
8.                 if i == 0 and j == 0:
   
9.                     dp[i][j] = True
   
10.                     continue
    
11.                     
    
12.                 if j == 0:
    
13.                     dp[i][j] = False
    
14.                     continue
    
15.                     
    
16.                 if p[j - 1] != '*':
    
17.                     if i > 0 and (p[j - 1] == s[i - 1] or p[j - 1] == '?'):
    
18.                         dp[i][j] |= dp[i - 1][j - 1]
    
19.                
    
20.                 else:
    
21.                     dp[i][j] |= dp[i][j - 1]
    
22.                     
    
23.                     if i > 0:
    
24.                         dp[i][j] |= dp[i - 1][j]
    
25.                
    
26.         return dp[m][n]

复制代码