leetcode-44. 通配符匹配刷题笔记（c++）

水深无声 2023-02-23 07:55 21阅读 0赞

#### 写在前面 ####

*  难度：困难
 *  `双指针法 + 2个临时变量`，局部回溯迭代
    
     *  测试用例多的题目，难度相对大

#### 题目详情 ####

给定一个字符串 (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

#### ac代码 ####

*  解题思路
    
     *  双指针法
        
         *  s：主字符串，p：字符模式
            
             *  1.字符相等或通配字符等于`'?'`,下1字符循环
             *  2.通配字符等于`'*'`,记录字符、通配字符位置，通配字符进入下1循环
             *  3.字符不等，当前字符均为非通配符且历史出现过`'*'`通配符，则主字符串进入下1字符循环（`字符模式下标不变`）
             *  4.其他，则返回false，通配失败
                
                 *  字符模式存在剩余字符，迭代排除`'*'`号字符
             *  5.比较通配长度与字符串`s`长度是否一致，一致则通配成功

class Solution {
        
    public:
        bool isMatch(string s, string p)
        {
        
            unsigned int i=0, j=0, s_cnt=-1, p_cnt=-1;
            while(i<s.size())
            {
        
                if(j<p.size() && (s[i]==p[j] || p[j]=='?'))
                {
        
                    i++;
                    j++;
                }
                else if(j<p.size() && p[j]=='*')
                {
        
                    s_cnt = i;
                    p_cnt = j;
                    j++;
                }
                else if(p_cnt != -1)
                {
        
                    j = p_cnt + 1;
                    i = ++s_cnt;
                }
                else
                    return false;
            }
    
            while(j<p.size() && p[j]=='*')
                j++;
    
            return j == p.size();
        }
    };

*  参考文章
    
     *  [44. 通配符匹配/C++][44. _C]
        
         *  动态规划方法，待学习
     *  [leetcode 44. 通配符匹配（C++）][leetcode 44. _C]

[44. _C]: https://blog.csdn.net/Zolewit/article/details/97629465
[leetcode 44. _C]: https://blog.csdn.net/nanashi_F/article/details/105165065