Sitch's Blog
0%

LeetCode-No-44

发表于 分类于 Valine：

通配符匹配

------类似No.10的正则匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

题目分析

和正则一样, 重点在于 * 的任意位匹配

  1. 假如是一个没有 * 的串匹配, 我们只要碰到一个匹配失败即可结束

  2. 有了 的情况, 可以用来干什么呢?-----帮你把匹配失败的地方干掉

  3. 因此其实我们可以先正常逐个精确匹配, 遇到 * 可以记录下来, 以便帮助后面

  4. 当在某一位精确匹配失败时, 我们回去找 的帮助, 如果之前没有 , 帮不了, 匹配失败

  5. 假如之前有 ,即需让往后匹配来避免这个失败位, 但是因为* 每向后扩展一位, 原本的精确匹配顺序全都挪动了一位, 此时我们不知道是不是能匹配成功

  6. 因此 帮忙的时候, 只向后扩展一位试试, 此时是一个未知的匹配状态, 我们需要在 * 的边缘重新开始精确匹配, 再失败了就重复 6 即可

题解代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    bool isMatch(string s, string p) 
    {
        //i,j指示当前匹配位置,iflag,jflag指示*号匹配位置
        int slength=s.length();
        int plength=p.length();
        int i=0;
        int j=0;
        int iflag=-1;
        int jflag=-1;

        //匹配到*之后的匹配中, 如果准确匹配,则进入了第一个if,失败则
        //  是* 则先保存现场, 在之后的匹配中如果失败则需要*来救场
        //  不是* ,则看之前有没有*,有可以用来救场,尝试增加*解决掉的位数,再继续试试
        // 没有*救场 , 那可以自闭了.over

        //循环内每次都确保当前匹配成功
        //注意j<plength的处理,j==plength时,仍然要继续尝试用*解决的,不能无脑return false.
        while(i<slength)
        {   
            //准确匹配成功
            if(j<plength && (s[i]==p[j] || p[j]=='?'))
            {
                i++;
                j++;

            }
            //匹配到*
            else if(j<plength && p[j]=='*')
            {
                iflag=i;
                jflag=j;

                //p中*用掉了,j去下一位. s[i]因为 *可能用于匹配空串,所以暂时不移动
                j++;
                
            }

            //准确匹配失败,但是进入下面的elseif内则说明之前有*,这时候就需要增加*匹配的一位 来尝试解决掉不能准确匹配的东西.
            else if(jflag!=-1)
            {   
                //*匹配到原iflag走不通,尝试匹配到iflag++位置,再次开始匹配
                i=++iflag;

                //p因为是用*去匹配的,所以p下一个要匹配的位是*下一位,jflag+1
                j=jflag+1;
            }

            //连*都不能帮忙解决,s可以走了
            else
                return false;
        }

        //注意考虑s匹配完了,p剩余*则还能成功
        while(j<plength)
            if(p[j]=='*')
                j++;
            else
                break;
        
        return j==plength;
    }
};