leetcode44.通配符匹配

Posted on | In |
Words count in article: 573 | Reading time ≈ 2

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

1
2
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

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

示例：

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

分析：
$$
\
题解1：和第十题类似，双字符串匹配问题，可以用动态规划来做。\
状态表示：\
dp[i][j]代表s的前i个字符和p的前j个字符是否匹配。\
状态初始化：dp[0][0] = true，对于1 <= i <= m如果p[i - 1] = ‘‘ && dp[0][i - 1]那么dp[0][i] = true，这对应着p以*as开头的字符串，因为可以代表0个字符，所以可以往后匹配。\

状态转移：\
s[i - 1] == p[j - 1] || p[j - 1] == ‘?’，这时候是精准匹配，所以取决于s的前i - 1个字符和p的前j - 1个字符是否匹配。dp[i][j] = dp[i - 1][j - 1];\
p[j - 1] == ‘‘，这个时候可以代表空串或者任意多个字符。\
如果是空串，那么dp[i][j] = dp[i][j - 1]\
如果不是空串，那么dp[i][j] = dp[i - 1][j]。这是因为代表了任意多个字符，如果能匹配前i - 1个字符，那么就在代表的字符串后面加上s[i]，就可以匹配前i个字符啦。\
$$

1
模板题：高精度乘法

代码

  • C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = " " + s, p = " " + p;

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;

        for (int i = 0;i <= n;i ++)
            for (int j = 1;j <= m;j ++) {
                if (p[j] != '*')
                    f[i][j] = i && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');
                else {
                    f[i][j] = f[i][j - 1] || i && f[i - 1][j];
                }
            }

        return f[n][m];
    }
};

[原题链接](44. 通配符匹配 - 力扣（Leetcode）)

0%