☆打卡算法☆LeetCode 44、通配符匹配算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串和一个字符模式，实现一个通配符匹配。”

题目链接：

来源：力扣（LeetCode）

链接：44. 通配符匹配 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

代码语言：javascript复制

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

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

代码语言：javascript复制

示例 1：
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

代码语言：javascript复制

示例 2：
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

二、解题

1、思路分析

这个题跟正则表达式匹配还是很像的，但是相对而已本题还是简单一些。

首先，模式p中任意字符都是独立的，不会与其他字符相互关联，比说说小写字母a-z都是匹配一个小写字母，问号？可以匹配任意一个小写字母，但是星号* 的匹配是不确定的，需要枚举所有的匹配情况。

为了减少重复枚举，我们可以使用双指针来解决本题。

2、代码实现

代码参考：

代码语言：javascript复制

public class Solution {
    public bool IsMatch(string s, string p) {
        int i = 0;//指向字符串s
        int j = 0;//指向字符串p
        int startPos = -1;//记录星号的位置
        int match = -1;//用于匹配星号
        while(i < s.Length){
            //表示相同或者p中为?
            if(j < p.Length &amp;&amp; (s[i] == p[j] || p[j] == '?')){
                i  ;
                j  ;
            }
            //匹配到了星号，记录下的位置
            else if(j < p.Length &amp;&amp; p[j] == '*'){
                startPos = j;
                match = i;
                j = startPos   1;
            }
            //以上都没有匹配到，回到星号所在的位置，往后再次匹配
            else if(startPos != -1){
                match  ;
                i = match;
                j = startPos   1;                
            }
            else{
                return false;
            }
        }
        //去除多余的星号
        while(j < p.Length &amp;&amp; p[j] == '*')j  ;
        return j==p.Length;
    }
}