一、题目
1、算法题目
“给定一个字符串和一个字符模式，实现一个通配符匹配。”
题目链接：
来源：力扣（LeetCode）
链接：44. 通配符匹配 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。 复制代码
两个字符串完全匹配才算匹配成功。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1： 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 复制代码
示例 2： 输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。 复制代码
二、解题
1、思路分析
这个题跟正则表达式匹配还是很像的，但是相对而已本题还是简单一些。
首先，模式p中任意字符都是独立的，不会与其他字符相互关联，比说说小写字母a-z都是匹配一个小写字母，问号？可以匹配任意一个小写字母，但是星号* 的匹配是不确定的，需要枚举所有的匹配情况。
为了减少重复枚举，我们可以使用双指针来解决本题。
2、代码实现
代码参考：
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 && (s[i] == p[j] || p[j] == '?')){ i++; j++; } //匹配到了星号，记录下的位置 else if(j < p.Length && 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 && p[j] == '*')j++; return j==p.Length; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(mn)
其中m和n分别是字符串和模式的长度。
空间复杂度： O(mn)
只需要存储所有m+n个状态需要的空间。
三、总结
忘了正则表达式匹配是怎么做的，可以返回去看一下# ☆打卡算法☆LeetCode 10、实现正则表达式匹配 算法解析
当然，想算法很爽，写算法很难受，这就叫做思想的巨人，行动的矮人嘛。。
