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).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false这道题通配符匹配问题还是小有难度的，这道里用了贪婪算法Greedy Alogrithm来解，由于有特殊字符*和？，其中？能代替任何字符，*能代替任何字符串，那么我们需要定义几个额外的指针，其中scur和pcur分别指向当前遍历到的字符，再定义pstar指向p中最后一个*的位置，sstar指向此时对应的s的位置，具体算法如下：
– 定义scur, pcur, sstar, pstar
– 如果*scur存在
– 如果*scur等于*pcur或者*pcur为 ‘?’，则scur和pcur都自增1
– 如果*pcur为’*’，则pstar指向pcur位置，pcur自增1，且sstar指向scur
– 如果pstar存在，则pcur指向pstar的下一个位置，scur指向sstar自增1后的位置
– 如果pcur为’*’，则pcur自增1
– 若*pcur存在，返回False，若不存在，返回True
C 解法一：
代码语言：javascript复制bool isMatch(char *s, char *p) {
char *scur = s, *pcur = p, *sstar = NULL, *pstar = NULL;
while (*scur) {
if (*scur == *pcur || *pcur == '?') {
scur;
pcur;
} else if (*pcur == '*') {
pstar = pcur ;
sstar = scur;
} else if (pstar) {
pcur = pstar 1;
scur = sstar;
} else return false;
}
while (*pcur == '*') pcur;
return !*pcur;
}这道题也能用动态规划Dynamic Programming来解，写法跟之前那道题Regular Expression Matching很像，但是还是不一样。外卡匹配和正则匹配最大的区别就是在星号的使用规则上，对于正则匹配来说，星号不能单独存在，前面必须要有一个字符，而星号存在的意义就是表明前面这个字符的个数可以是任意个，包括0个，那么就是说即使前面这个字符并没有在s中出现过也无所谓，只要后面的能匹配上就可以了。而外卡匹配就不是这样的，外卡匹配中的星号跟前面的字符没有半毛钱关系，如果前面的字符没有匹配上，那么直接返回false了，根本不用管星号。而星号存在的作用是可以表示任意的字符串，当然只是当匹配字符串缺少一些字符的时候起作用，当匹配字符串包含目标字符串没有的字符时，将无法成功匹配。
C 解法二：
代码语言：javascript复制class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), 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 {
dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};类似题目：
Regular Expression Matching
参考资料：
https://discuss.leetcode.com/topic/3040/linear-runtime-and-constant-space-solution
https://discuss.leetcode.com/topic/40118/clear-c-dp-solution-similar-to-the-last-matching-problem
LeetCode All in One 题目讲解汇总(持续更新中…)
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/109497.html原文链接：https://javaforall.cn
