题目描述
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example2:
Input: s = "aa" p = "*" Output: true Explanation: '*' matches any sequence.
Example3:
Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example4:
Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example5:
Input: s = "acdcb" p = "a*c?b" Output: false
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 *.
解题思路
- dp
- dp[i][j], 状态数组，表示从s的i到p的j是否可以匹配
- 当 p上一个字符为’？’或者p上一个字符等于s上一个字符，则当前真值与上一位相同
- p上一个字符为’‘时，则可表示p往后走一位或者s往后走一位
- 当p[j] == * 时，因为 * 可以匹配任何字符串，所以只要前半部分能匹配，后面的都行 ,dp[i][j]=dp[i-1][j] or dp[i][j-1 ],在dp[i][j]=dp[i-1][j]中( * 表示空串)，dp[i][j]=l[i][j-1]中( * 表示任意字符串 )，两者有一个符合即可
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for(int i = 1; i <= n; i++){
if(p[i - 1] == '*'){
dp[0][i] = dp[0][i - 1];
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(p[j - 1] == '*'){
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}else if(s[i - 1] == p[j - 1] || p[j - 1] == '?'){
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
