44.Wildcard Matching¶
Tags: Hard Greedy String Backtracking Dynamic Programming
Links: https://leetcode.com/problems/wildcard-matching/
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).
Note:
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like?or*.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
class Solution {
public:
bool isMatch(string s, string p) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//iStar记录s与*匹配的位置，jStar记录p中*的位置
int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size();
while (i < m) {
if (j < n && (s[i] == p[j] || p[j] == '?')) {
++i; ++j;
}
else if (j < n && p[j] == '*') { //*什么都不匹配
iStar = i;
jStar = j++;
}
else if (iStar >= 0) { //*至少匹配一个字符
i = ++iStar;
j = jStar + 1;
}
else return false;
}
//可能存在p中的*把s都匹配了，但是p中还剩余不是*的字符未匹配
while (j < n && p[j] == '*') ++j;
return j == n;
}
};
时间复杂度O(n)，贪心的策略。用iStar 记录s与*匹配的位置， jStar记录p中*的位置，初始化为-1来进行标识。
首先如果s[i] == p[j] || p[j] == '?'，意味着可以完成正常一对一匹配，所以i和j的位置增加即可。
如果遇到了p[j] == '*'的情况，那么就要区别对待，因为*可以匹配0个或者多个字符。如果*什么都不匹配，用iStar和jStar记录下遇到*的各自的位置，然后让j的位置增加看能否继续匹配。另外一种情况是*至少匹配一个字符，那么让iStar增加一个单位，意味着在字符串s中至少有一个字符被匹配，于是去检验下一个能否被匹配，其实相当于一个回退的功能。
举例说明：设s = aab, p = a*c，这里假如s的第二个a和p的*匹配，那么iStar = 1, jStar = 1，发现b和c不匹配，于是iStar = 2意味着*匹配了两个字符，这样就到了末尾。
最后检查字符串p还是没有到末尾，所以无法完成匹配。
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> d(m + 1, vector<bool>(n + 1, false));
d[0][0] = true; //s和p都为空，完成匹配
//预处理s为空，p为连续*的情况
for (int i = 1; i <= n; ++i) {
if (p[i - 1] == '*')
d[0][i] = true;
else
break;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == p[j - 1] || p[j - 1] == '?')
d[i][j] = d[i - 1][j - 1];
else if (p[j - 1] == '*')
d[i][j] = d[i - 1][j] | d[i][j - 1];
}
}
return d[m][n];
}
};
还可以从动态规划的角度去求解问题，为了求解问题方便，下标从1开始计数（也就是1对应着字符串中的0的位置）。用d[i][j]表示字符串s的前i个字符和字符串p的前j个字符是否完成匹配。然后去寻找状态转移方程。
假如在在字符串的第i个位置和字符串p的第j个位置相同或j的位置为?，那么只需要去考察d[i - 1][j - 1]。
如果在p中的位置j处是*，那么*的作用可以匹配，也可以什么都不匹配。假如什么都不匹配，则依赖于d[i][j - 1]，当前完成匹配，还可以继续匹配多个，那么依赖于d[i - 1][j]。
完成初始化工作，如果初始两个字符串都为空，那么肯定可以完成匹配。另外考虑字符串s初始为空，而字符串p有前导的*，比如*****aa，那么这些前导的*的部分其实可以完成匹配，也就是*匹配0个字符，所以需要对这个部分完成初始化。
时间复杂度是O(mn)。