LeetCode 0044 - Wildcard Matching
# Hints
- DP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
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:
s
could be empty and contains only lowercase lettersa-z
.p
could 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
# 题意
给定一个输入串 和一个模式串 ,其中 仅包含小写字母, 包含小写字母和特殊字符 '?'
和 '*'
。要求实现支持如下功能的通配符模式匹配:
'?'
可以匹配任意单个字符。'*'
可以匹配任意字符串(包括空串)。
# 题解
首先我们不难意识到任意个数的 '*'
组成的连续子串都是等价的,例如 "*"
和 "***"
在匹配时没有任何区别。
考虑动态规划,设 表示 和 是否可以匹配。
状态转移方程:
则 即为答案。其中 意为 是否满足子串的每个字符均为 '*'
。
下面我们详细解释这个复杂的状态转移方程。
首先考虑初始状态。
空输入串和空模式串一定可以匹配,所以 。
非空输入串和空模式串一定不能匹配,所以 。
空输入串和非空模式串可以匹配,当且仅当 均为 '*'
字符,因为只有 '*'
可以与空串匹配,所以 ,其中 的定义如上所述。
然后考虑状态转移的两种情况。
当 和 直接匹配时,即 或 为 '?'
时,显然 。
当 为 '*'
时,不难发现,如果 可以和 匹配,则必须满足两个条件之一:
要么 可以和 匹配;
s: abcd
p1: abcd*
p2: a**b*cd*
要么存在子串 可以和 匹配;
s1: abcd
s2: abcde
s3: abcdefghij
p: abcd*
由此可得 。
事实上,从上面的例子即可看出,因为 abcd*
总是能匹配 abcd
任意长度任意内容的后续内容,所以我们直接考虑子串 是否可以和 匹配即可,无需枚举 以进行冗余的判断,由此可得 。
总的时间复杂度为 。
# AC代码
class Solution {
public:
bool isMatch(const string & s, const string & p) {
// 初始化
int n = s.length();
int m = p.length();
bool dp[n + 1][m + 1];
memset(dp, false, sizeof(dp));
// 递推
dp[0][0] = true;
for (int i = 1; i <= n; i ++) {
dp[i][0] = false;
}
for (int j = 1; j <= m && p[j - 1] == '*'; j ++) {
dp[0][j] = true;
}
for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) {
if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
}
}
// 返回
return dp[n][m];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01