leetcode 44. 通配符匹配
题目描述
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符?和*。
示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。
示例 3:
输入: s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入: s = "adceb" p = "*a*b" 输出: true 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入: s = "acdcb" p = "a*c?b" 输出: false
题解——充分剪枝的回溯法
我用回溯法写题目,很少有一次通过的😂,经常会TLE
不过,我有一个信念,那就是——充分剪枝的回溯法,效率上不会比dp差
难就难在该如何剪枝。
但为什么还要用回溯法来写呢？因为回溯的模板很好掌握(也因为我现在大一还没学过算法,不太会dp😁),也就是说,很容易就能写出正确但超时的代码,然后在此基础之上进行剪枝即可
通过这道题来浅析一下回溯剪枝的一些方法
我们要意识到,不经剪枝的回溯与穷举差不了多少,而剪枝的过程就是缩小解空间的过程
如何缩小解空间呢?两个方向,一个是搜索过的状态不重复搜索,主要通过哈希表去重实现;另一个是可以排除的状态不去搜索,就要具体题目具体分析,看看如何排除尽可能多的状态了
先看一下最开始的朴素的回溯法是怎么做的
原始模板
1 | //思路:回溯,主要考虑*匹配多少个字符 |
提交一下,死在了1616个用例这里(不经剪枝的回溯,其实不必抱有通过的希望🤣)
哈希表去重
下面尝试使用哈希表去重,用一个集合记录已经查找过的{pos1,pos2}对,如果找过了,就不再找了,这样可以大大减少重复运算
代码如下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
34
35class Solution {
public:
bool ans=false;
set<pair<int,int>> tried;//哈希表去重
void solve(string &s,string &p,int pos1,int pos2)
{
if(ans==true)
return ;
if(tried.find(pair<int,int>{pos1,pos2})!=tried.end())//找过了
return ;
tried.insert({pos1,pos2});//没找过,记录
if(pos1==s.size()&&pos2==p.size())
ans=true;
else
{
while(pos1<s.size()&&pos2<p.size()&&(s[pos1]==p[pos2]||p[pos2]=='?'))//找到第一个不能匹配的地方
{
++pos1;
++pos2;
}
if(pos1==s.size()&&pos2==p.size())//匹配成功
ans=true;
else if(p[pos2]=='*')//不能匹配的地方是*
{
int cnt=0;
while(pos1+cnt<=s.size())
solve(s,p,pos1+cnt++,pos2+1);
}
}
}
bool isMatch(string s, string p) {
solve(s,p,0,0);
return ans;
}
};
提交一下,竟然过了,用时600ms。所以,我们应该记住,只要写回溯法,就加上哈希表去重的工作,这样可能就直接过了(用unordered_set应该更好,但要手写哈希函数,还是算了)
优化
虽然过了,但这速度显然可以继续优化
首先,对于连续出现的*,可以视为一个,其次,在*匹配时,应该确保下一个可以匹配才继续
可以优化如下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
34
35
36
37
38
39
40
41
42//思路:回溯,主要考虑*匹配多少个字符
class Solution {
public:
bool ans=false;
set<pair<int,int>> tried;//哈希表去重
void solve(string &s,string &p,int pos1,int pos2)
{
if(ans==true)
return ;
if(tried.find(pair<int,int>{pos1,pos2})!=tried.end())
return ;
tried.insert({pos1,pos2});
if(pos1==s.size()&&pos2==p.size())
ans=true;
else
{
while(pos1<s.size()&&pos2<p.size()&&(s[pos1]==p[pos2]||p[pos2]=='?'))//找到第一个不能匹配的地方
{
++pos1;
++pos2;
}
if(pos1==s.size()&&pos2==p.size())//匹配成功
ans=true;
else if(p[pos2]=='*')//不能匹配的地方是*
{
while(pos2<p.size()-1&&p[pos2+1]=='*')//过滤掉连续的*
++pos2;
int cnt=0;
while(pos1+cnt<=s.size())
{
if((pos1+cnt==s.size()&&pos2+1==p.size())||(s[pos1+cnt]==p[pos2+1]||p[pos2+1]=='?'))
solve(s,p,pos1+cnt,pos2+1);//下一个能匹配,才尝试
++cnt;
}
}
}
}
bool isMatch(string s, string p) {
solve(s,p,0,0);
return ans;
}
};
这样,可以优化到100ms以内
最强的去重方法
对于这道题来说,搜索广度主要取决于*匹配的个数,所以,应该尽可能安排合理的个数
在前面的写法里,*的尝试是从0个到最后一个,但是仔细一想是不合理的,因为p后面的字符串也必须被匹配到
所以,我们应该保证待匹配的s比待匹配的q长,否则是不可能成功的
不过,因为*可以不匹配任何字符,所以应该改成待匹配的s比带匹配的q除去*的长度要长
为此,我们引入一个stars,用来记录剩下的*的个数,每走过一个*,就-1
特别地,这样剪枝之后,重复量小到哈希表显得多余了,去掉反而更快
提交之后,得到了开头那张图上的0ms,之后的提交也稳定在0~8ms之间了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
34
35
36
37
38
39
40
41
42
43class Solution {
public:
bool ans=false;
int stars=0;
void solve(string &s,string &p,int pos1,int pos2)
{
if(ans==true)
return ;
if(pos1==s.size()&&pos2==p.size())
ans=true;
else
{
while(pos1<s.size()&&pos2<p.size()&&(s[pos1]==p[pos2]||p[pos2]=='?'))//找到第一个不能匹配的地方
{
++pos1;
++pos2;
}
if(pos1==s.size()&&pos2==p.size())//匹配成功
ans=true;
else if(p[pos2]=='*')//不能匹配的地方是*
{
while(pos2<p.size()-1&&p[pos2+1]=='*')//连续的*效果相同,跳过,同时--stars
{
--stars;
++pos2;
}
--stars;
int cnt=0;
while(s.size()-pos1-cnt+1>=p.size()-pos2-stars)//要给p后面的留足空间
{
if((pos1+cnt==s.size()&&pos2+1==p.size())||(s[pos1+cnt]==p[pos2+1]||p[pos2+1]=='?'))//下一个能匹配,才尝试
solve(s,p,pos1+cnt,pos2+1);
++cnt;
}
}
}
}
bool isMatch(string s, string p) {
for_each(p.begin(),p.end(),[&](char &c){ if(c=='*') ++stars;});//统计*的个数
solve(s,p,0,0);
return ans;
}
};
