Leetcode-44-通配符匹配

发表于 | 分类于

题目

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

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

说明:

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

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

输入:
s = “aa”
p = ““
输出: true
解释: ‘‘ 可以匹配任意字符串。
示例 3:

输入:
s = “cb”
p = “?a”
输出: false
解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
示例 4:

输入:
s = “adceb”
p = “ab”
输出: true
解释: 第一个 ‘‘ 可以匹配空字符串, 第二个 ‘‘ 可以匹配字符串 “dce”.
示例 5:

输入:
s = “acdcb”
p = “a*c?b”
输出: false

动态规划

可以用动态规划的思想来解决此题.

假设dp[i][j]表示字符串s的前i个字符和模式p的前j个字符能否匹配.

那么就有:

  1. 若p[j]是*, 说明模式p对字符串没有任何要求, 若*匹配的是空字符串, 则说明当前dp[i][j]依赖于dp[i][j-1]. 如果*匹配的不是空字符串, 那么dp[i][j]则依赖于dp[i-1][j]. 即转移方程为:

  2. 若p[j]是?, 说明模式p可以匹配任何一个字符, 当前字符匹配的结果取决于前一个字符匹配的结果. 动态转移方程为:

  3. 若p[j]是小写字母(最后剩下的情况), 那么s[i]和p[j]必须是相同的字母, 动态转移方程为:

接下来看一下dp数组的边界情况.

  1. 当i=j=0时, 用空模式去匹配空字符串, 结果必然为真, 即dp[0][0]=true
  2. 当j=0, i!=0时, 用空模式去匹配非空字符串, 结果必然为假, 即dp[i][0]=false
  3. 当i=0, j!=0时, 用模式去匹配空字符串, 此时只有模式在j之前都为*才为真.

具体代码如下

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
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();

        // 初始化dp
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = true;
            } else {
                break;
            }
        }

        // dp迭代
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else if (p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1)) && dp[i - 1][j - 1];
                }
            }
        }

        return dp[m][n];
    }
}