leetcode44

 1 class Solution {
 2     public boolean isMatch(String s, String p) {
 3         if (p == null || p.length() == 0) {
 4             return s == null || s.length() == 0;
 5         }
 6         boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
 7         dp[0][0] = true;
 8         int i, j;
 9 
10         for (i = 1; i <= p.length(); i++) {
11             if (p.charAt(i - 1) == '*') {
12                 dp[0][i] = true;
13             } else {
14                 break;
15             }
16         }
17 
18         for (i = 1; i <= s.length(); i++) {
19             for (j = 1; j <= p.length(); j++) {
20                 // the letter of p[j] exactly match with s[i] or is '?'
21                 if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
22                     dp[i][j] = dp[i - 1][j - 1];
23                 }
24 
25                 // the letter of p is '*'
26                 if (p.charAt(j - 1) == '*') {
27                     /*
28                      * dp[i][j] = dp[i][j-1] means '*' act as empty card dp[i][j] = dp[i-1][j] means
29                      * '*' act as wild card to match with s[i]
30                      */
31                     dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
32                 }
33             }
34         }
35         return dp[s.length()][p.length()];
36     }
37 }

参考：https://leetcode.com/problems/wildcard-matching/discuss/429337/Java%3A-Wild-card!

补充一个python的实现：

 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         dp[0][0] = True
 6         
 7         for j in range(1,n+1):
 8             if p[j-1] == '*':
 9                 dp[0][j] = True
10             else:
11                 break
12         for i in range(1,m+1):
13             for j in range(1,n+1):
14                 if s[i-1] == p[j-1] or p[j-1] == '?':
15                     dp[i][j] = dp[i-1][j-1]
16                 elif p[j-1] == '*':
17                     dp[i][j] = dp[i-1][j] or dp[i][j-1]
18         # print(dp)
19         return dp[m][n]

思路：动态规划。

举例分析：s='acdcb' p='a*c?b' 。s长度为m，p长度为n。

初始化二维数组dp，有m+1行，n+1列。

dp[0][0] = True，先设置第0行，如果p中对应字符是‘*’，则设置为True，遇到非'*'后面都设置为False。

从第1行开始，如果s与p中对应字符是相同或者p中是'?'，则dp取其'左上角'元素的值。

如果p中的字符是'*'，则dp判断其'上方'和'左侧'的逻辑或，(即上方或左侧是否为True)。