题目
Given an input string (s) and a pattern
(p), implement wildcard pattern matching with support for
'?' and '*'.
1
2
| '?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
|
The matching should cover the entire input string
(not partial).
Note:
s could be empty and contains only lowercase letters
a-z.p could be empty and contains only lowercase letters
a-z, and characters like ? or
*.
Example 1:
1
2
3
4
5
| Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
|
Example 2:
1
2
3
4
5
| Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
|
Example 3:
1
2
3
4
5
| Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
|
Example 4:
1
2
3
4
5
| Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
|
Example 5:
1
2
3
4
| Input:
s = "acdcb"
p = "a*c?b"
Output: false
|
题解
动态规划，转移方程：
dp[i][j]表示字符串 s 的前 i 个字符和模式 p 的前 j
个字符是否能匹配。
边界，dp[0][0]=true,\(dp[0][j]\)只有模式p前j个全是*才能匹配。
\[
dp[i][j]=\begin{cases}
dp[i-1][j-1] \quad s[i]==p[i] or p[i]=='?'\\
dp[i-1][j]\vee dp[i][j-1] \quad p[j]=='*'\\
false \space \quad 其他情况
\end{cases}
\]
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
|
class Solution {
public:
bool isMatch(string s, string p) {
int m=s.length();
int n=p.length();
vector<vector<int>> dp(m+1,vector<int>(n+1));
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
if(p[i-1]=='*') dp[0][i]=1;
else break;
}
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
if(p[j-1]=='?' || s[i-1]==p[j-1]){
dp[i][j]=dp[i-1][j-1];
}else if(p[j-1]=='*'){
dp[i][j]=dp[i-1][j]|dp[i][j-1];
}
}
}
return dp[m][n];
}
};
|