通配符匹配
题面
leetcode题目
给定一个字符串 \(s\) 和一个字符模式 \(p\) ，实现一个支持 '?$ 和 \('*'\) 的通配符匹配。
\('?'\) 可以匹配任何单个字符。
\('*'\) 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
* \(s\) 可能为空，且只包含从 \(a-z\) 的小写字母。
* \(p\) 可能为空，且只包含从 \(a-z\) 的小写字母，以及字符 \(?\) 和 \(*\)。
example-1
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
example-2
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
题解
总体思路
类似于前文(leetcode-10-正则表达式匹配)中提到的思路，与前文不同的是此处需要支持*的匹配，我们可以看出对于*来讲，如果满足\(dp[i-1][r] == 1\)，则都可以将\(p[r+1...j]\)中间的这一段与*进行匹配，思路是类似的。
!!! note 注意
这道题也要比较小心的处理\(dp[0]\)的初始化问题。
!!! note 注意
下文解法中对于\(dp[r][j-1]\)的处理比较粗糙，可以继续优化。
代码
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| #include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;
bool match(char a, char b)
{
return a == b || b == '?';
}
class Solution
{
public:
bool isMatch(string s, string p)
{
int lens = s.length();
int lenp = p.length();
int dp[lens + 1][lenp + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int j = 1; j <= lenp; j++)
{
if (p[j - 1] == '*' && dp[0][j - 1] == 1)
{
dp[0][j] = 1;
}
}
for (int i = 1; i <= lens; i++)
{
for (int j = 1; j <= lenp; j++)
{
if (p[j - 1] == '*')
{
for (int r = 0; r <= i; r++)
{
if (dp[r][j - 1] == 1)
{
dp[i][j] = 1;
break;
}
}
}
else if (match(s[i - 1], p[j - 1]) && dp[i - 1][j - 1] == 1)
{
dp[i][j] = 1;
}
}
}
#ifdef DEBUG
for (int i = 0; i <= lens; i++)
{
for (int j = 0; j <= lenp; j++)
{
cout << dp[i][j] << " ";
}
cout << endl;
}
#endif
return dp[lens][lenp] == 1;
}
};
int main()
{
Solution s;
cout << s.isMatch("aa", "a") << endl;
cout << s.isMatch("aa", "*") << endl;
cout << s.isMatch("cb", "?a") << endl;
cout << s.isMatch("adceb", "a*b") << endl;
cout << s.isMatch("acdcb", "a*c?b") << endl;
cout << s.isMatch("aab", "c*a*b") << endl;
cout << s.isMatch("adceb", "*a*b") << endl;
return 0;
}
|