题目描述
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
题解
或许，你需要来个动态规划？
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
26
27
28
29
30
31
32
33
| bool isMatch(string s, string p) {
int len1 = s.length();
int len2 = p.length();
bool** value = new bool*[len1+1];
for (int i = 0; i <= len1; i++)
{
value[i] = new bool[len2 + 1];
value[i][0] = false;
}
value[0][0] = true;
for (int i = 1; i <= len2; i++)
{
switch (p[i-1])
{
case '*':
value[0][i] = value[0][i - 1];
for (int j = 1; j <= len1; j++)
value[j][i] = value[j - 1][i] || value[j][i - 1];
break;
case '?':
value[0][i] = false;
for (int j = 1; j <= len1; j++)
value[j][i] = value[j - 1][i - 1];
break;
default:
value[0][i] = false;
for (int j = 1; j <= len1; j++)
value[j][i] = value[j - 1][i - 1] && p[i - 1] == s[j - 1];
break;
}
}
return value[len1][len2];
}
|
我要挂一个过分的例子
“abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb”
“**aa****ba\a*bb\aa*ab****aaaaaaa\**a*aaaa**bbabb*b*b**aaaaaaaaa*a*******ba*bbb***a*ba*bb*bb\abbb”
他害我写的递归超时了。
还是怪我，动态规划学得不到位。