二维动态规划解决通配符匹配问题

题目链接-来源：力扣（LeetCode）

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

思路：

此题与 10.正则表达式匹配 相当类似，整体而言更加简单，我们可以借鉴其思路来破解本题。
我们同样记 f(i, j) 为模式串的前 i - 1 个字符与字符串的前 j - 1 个字符的匹配情况。其中 f(0, j) 与 f(i, 0) 分别表示模式串或字符串为空串的情形。
对于普通字符，f(i, j) 成立当且仅当 f(i - 1, j - 1) 成立，并且 s[j - 1] == p[i - 1]，即转移方程为 f(i, j) = f(i - 1, j - 1) && p[i - 1] == s[j - 1]。
对于 p[i - 1] == ‘?’，我们可以将其与普通字符归为一类处理，用一个 match(char a, char b) 函数表示两个字符匹配，而 ‘?’ 可以使得该函数一定返回 true。
对于 p[i - 1] == ‘*‘，我们单独考虑 2 类情况。
一是，当固定 p[i - 1] == ‘*‘ 不动时，我们考虑 s 添加了 s[j - 1] 的情况，即从 f(i , j - 1) 向 f(i, j) 的转移情况，显然，由于 ‘*‘ 能匹配任意串， 所以 s[j - 1] 并不影响我们的匹配状态，即有 f(i, j) = f(i, j - 1)。
二是，当固定 s[j - 1]，考虑 p 添加了 p[i - 1] 并且 p[i - 1] == ‘*‘，由于 ‘*‘ 能够匹配空串，所以添加 p[i - 1] 同样不影响我们的匹配状态，即在上式的基础上有 f(i, j) = f(i - 1, j) || f(i, j - 1)。
综上，我们已经完成了两种状态转移方程，将两者结合，更新 f(i, j)即可。
考虑边界条件，空串可以与空串匹配，因此有 f(0, 0) = true；而非空字符串与空串必然不匹配，因此有 f(0, j) = false；对于非空模式串与空串的情形，只需考虑 p[i - 1] == ‘*‘的情形，因为添加 p[i - 1] 不会影响匹配状态，所以此时有 f(i, 0) = f(i - 1, 0)，而其他情况下，f(i, 0) = false。
时间复杂度：O(mn)
空间复杂度：O(mn)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public boolean isMatch(String s, String p) {
        int lenS = s.length(), lenP = p.length();
        
        // Bound
        if (lenS == 0 && lenP == 0) {
            return true;
        } else if (lenP == 0) {
            return false;
        }
        
        // Init
        
        boolean[][] dp = new boolean[lenP + 1][lenS + 1];
        dp[0][0] = true;
        for (int i = 1; i <= lenP; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[i][0] = dp[i - 1][0];
            }
        }
        
        // Solution
        
        for (int i = 1; i <= lenP; i++) {
            for (int j = 1; j <= lenS; j++) {
                if (match(p.charAt(i - 1), s.charAt(j - 1))) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(i - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        
        return dp[lenP][lenS];
    }
    
    private boolean match(char a, char b) {
        if (a == '?' || b == '?') {
            return true;
        }
        if (a == b) {
            return true;
        }
        return false;
    }
}