3.7通配符匹配

2024-06-08 05:18

文章标签 匹配 3.7 通配符

本文主要是介绍3.7通配符匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 1.题目
- 2.代码

1.题目

题目要求
思路：
那就是一旦p中有s中不存在的字符，那么一定无法匹配，因为星号只能增加字符，不能消除字符；
p串中星号的位置很重要，用 jStar 来表示，还有星号匹配到s串中的位置，使用 iStart 来表示，这里 iStar 和 jStar 均初始化为 -1，表示默认情况下是没有星号的；

2.代码

class Solution{
public:bool isMatch(string s, string p){int istart=-1,jstart=-1,s_length=s.size(),p_length=p.size();int i=0,j=0;开始进行匹配，若i小于s串的长度，进行 while 循环while (i<s_length){若当前两个字符相等，或着p中的字符是问号，则i和j分别加1if (j< p_length &&(s[i] == s[j] || p[j] == 'j')){++i;++j;}若 p[j] 是星号，要记录星号的位置，jStar 赋为j，此时j再自增1，iStar 赋为ielse if (j< p_length && p[j] == '*'){istart=i;jstart=j++;}若当前 p[j] 不是星号，并且不能跟 p[i] 匹配上，此时就要靠星号了，若之前星号没出现过，那么就直接跪，比如 s = "aa" 和 p = "c*"，此时 s[0] 和 p[0] 无法匹配，虽然 p[1] 是星号，但还是跪。如果星号之前出现过，可以强行续一波命，比如 s = "aa" 和 p = "*c"，当发现 s[1] 和 p[1] 无法匹配时，但是好在之前 p[0] 出现了星号，把 s[1] 交给 p[0] 的星号去匹配。else if (istart > 0){i=++istart;j=jstart+1;}else return false;}至于如何知道之前有没有星号，这时就能看出 iStar 的作用了，因为其初始化为 -1，而遇到星号时，其			就会被更新为i，只要检测 iStar 的值，就能知道是否可以使用星号续命。虽然成功续了命，匹配完了s中的所有字符，但是之后还要检查p串，此时没匹配完的p串里只能剩星号，不能有其他的字符，将连续的星号过滤掉，如果j不等于p的长度，则返回 falsewhile (j<p_length && p[j] == '*')++j;return j==p_length;}
};