通配符匹配问题：
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:
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 *.
待匹配字串 s 中只有字母，模式串中 p 只含有字母和 ?、*，? 匹配任意单个字符，* 匹配任意多个字符（包括空字串），判断字串是否完全匹配。
使用递归算法会超时。
动态规划
设 表示 s 前 个字符与 p 前 个字符是否匹配，当 时不难写出递推公式：
对边界情况提前做特殊处理即可。C 语言实现：
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
|
bool (char *s, char *p) {
if (s == NULL || p == NULL) return false;
const size_t len_s = strlen(s), len_p = strlen(p);
bool **match = (bool **) malloc((len_s + 1) * sizeof(bool *));
for (size_t i = 0; i <= len_s; ++i) match[i] = (bool *) calloc(len_p + 1, sizeof(bool));
match[0][0] = true;
for (size_t j = 1; j <= len_p; ++j) {
if (p[j - 1] == '*' && match[0][j - 1])
match[0][j] = true;
else break;
}
for (size_t i = 1; i <= len_s; ++i) {
for (size_t j = 1; j <= len_p; ++j) {
if (p[j - 1] == '?' || p[j - 1] == s[i - 1])
match[i][j] = match[i - 1][j - 1];
else if (p[j - 1] == '*')
match[i][j] = match[i][j - 1] || match[i - 1][j];
}
}
bool ret = match[len_s][len_p];
for (size_t i = 0; i <= len_s; ++i) free(match[i]);
free(match);
return ret;
}
|
时间复杂度为 。
贪心法
这里的贪心法其实可以看作是对递归版本算法（DFS）的优化，在递归版本中，当在模式串中遇到 * 时，是这样实现的：
1
2
|
if (p[j] == '*')
return isMatch(i, j + 1) || isMatch(i + 1, j);
|
即每遇到一个 * 均会产生一个分支，而贪心法则只对模式串上一个（已扫描部分的最后一个） * 进行继续搜索，实现时只要不断更新 * 的指针即可。C 语言实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
bool (char *s, char *p) {
if (s == NULL || p == NULL) return false;
char *star = NULL, *last_str = NULL;
while (*s != '
|
近期评论