算法leetcode｜44. 通配符匹配（rust重拳出击）

文章目录

44. 通配符匹配：

给定一个字符串 (

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

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 主要是星号匹配的处理，整体去看，比较迷茫，必须要分解问题，可以考虑动态规划。
• 在模式字符串中出现的字符和问号可以理解为是固定匹配的，而星号则需要暴力尝试，所以我们可以考虑把模式串按照星号分割，然后贪心的去尝试匹配字符和问号。

题解：

rust

implSolution{pubfnis_match(s:String, p:String)->bool{fnis_all_stars(bs:&[u8], left:usize, right:usize)->bool{for i in left..right {if bs[i]!=b'*'{returnfalse;}}returntrue;}fnis_char_match(u:u8, v:u8)->bool{
            u == v || v ==b'?'}let sbs = s.as_bytes();let pbs = p.as_bytes();let(mut s_right,mut p_right)=(s.len(), p.len());while s_right >0&& p_right >0&& pbs[p_right -1]!=b'*'{ifis_char_match(sbs[s_right -1], pbs[p_right -1]){
                s_right -=1;
                p_right -=1;}else{returnfalse;}}if p_right ==0{return s_right ==0;}let(mut s_index,mut p_index)=(0,0);let(mut s_record,mut p_record)=(-1i32,-1i32);while s_index < s_right && p_index < p_right {if pbs[p_index]==b'*'{
                p_index +=1;
                s_record = s_index asi32;
                p_record = p_index asi32;}elseifis_char_match(sbs[s_index], pbs[p_index]){
                s_index +=1;
                p_index +=1;}elseif s_record !=-1&& s_record +1< s_right asi32{
                s_record +=1;
                s_index = s_record asusize;
                p_index = p_record asusize;}else{returnfalse;}}returnis_all_stars(pbs, p_index, p_right);}}

go

funcisMatch(s string, p string)bool{
    charMatch :=func(u, v byte)bool{return u == v || v =='?'}
    allStars :=func(str string, left, right int)bool{for i := left; i < right; i++{if str[i]!='*'{returnfalse}}returntrue}forlen(s)>0&&len(p)>0&& p[len(p)-1]!='*'{ifcharMatch(s[len(s)-1], p[len(p)-1]){
            s = s[:len(s)-1]
            p = p[:len(p)-1]}else{returnfalse}}iflen(p)==0{returnlen(s)==0}
    sIndex, pIndex :=0,0
    sRecord, pRecord :=-1,-1for sIndex <len(s)&& pRecord <len(p){if p[pIndex]=='*'{
            pIndex++
            sRecord, pRecord = sIndex, pIndex
        }elseifcharMatch(s[sIndex], p[pIndex]){
            sIndex++
            pIndex++}elseif sRecord !=-1&& sRecord+1<len(s){
            sRecord++
            sIndex, pIndex = sRecord, pRecord
        }else{returnfalse}}returnallStars(p, pIndex,len(p))}

c++

classSolution{public:boolisMatch(string s, string p){auto allStars =[](const string &str,int left,int right){for(int i = left; i < right;++i){if(str[i]!='*'){returnfalse;}}returntrue;};auto charMatch =[](char u,char v){return u == v || v =='?';};while(s.size()&& p.size()&& p.back()!='*'){if(charMatch(s.back(), p.back())){
                s.pop_back();
                p.pop_back();}else{returnfalse;}}if(p.empty()){return s.empty();}int sIndex =0, pIndex =0;int sRecord =-1, pRecord =-1;while(sIndex < s.size()&& pIndex < p.size()){if(p[pIndex]=='*'){++pIndex;
                sRecord = sIndex;
                pRecord = pIndex;}elseif(charMatch(s[sIndex], p[pIndex])){++sIndex;++pIndex;}elseif(sRecord !=-1&& sRecord +1< s.size()){++sRecord;
                sIndex = sRecord;
                pIndex = pRecord;}else{returnfalse;}}returnallStars(p, pIndex, p.size());}};

c

bool allStars(char*str,int left,int right){for(int i = left; i < right;++i){if(str[i]!='*'){return false;}}return true;}

bool charMatch(char u,char v){return u == v || v =='?';};

bool isMatch(char*s,char*p){int len_s =strlen(s), len_p =strlen(p);while(len_s && len_p && p[len_p -1]!='*'){if(charMatch(s[len_s -1], p[len_p -1])){
            len_s--;
            len_p--;}else{return false;}}if(len_p ==0){return len_s ==0;}int sIndex =0, pIndex =0;int sRecord =-1, pRecord =-1;while(sIndex < len_s && pIndex < len_p){if(p[pIndex]=='*'){++pIndex;
            sRecord = sIndex;
            pRecord = pIndex;}elseif(charMatch(s[sIndex], p[pIndex])){++sIndex;++pIndex;}elseif(sRecord !=-1&& sRecord +1< len_s){++sRecord;
            sIndex = sRecord;
            pIndex = pRecord;}else{return false;}}returnallStars(p, pIndex, len_p);}

python

classSolution:defisMatch(self, s:str, p:str)->bool:defis_all_stars(st:str, left:int, right:int)->bool:returnall(st[i]=='*'for i inrange(left, right))defis_char_match(u:str, v:str)->bool:return u == v or v =='?'

        s_right, p_right =len(s),len(p)while s_right >0and p_right >0and p[p_right -1]!='*':if is_char_match(s[s_right -1], p[p_right -1]):
                s_right -=1
                p_right -=1else:returnFalseif p_right ==0:return s_right ==0

        s_index, p_index =0,0
        s_record, p_record =-1,-1while s_index < s_right and p_index < p_right:if p[p_index]=='*':
                p_index +=1
                s_record, p_record = s_index, p_index
            elif is_char_match(s[s_index], p[p_index]):
                s_index +=1
                p_index +=1elif s_record !=-1and s_record +1< s_right:
                s_record +=1
                s_index, p_index = s_record, p_record
            else:returnFalsereturn is_all_stars(p, p_index, p_right)

java

classSolution{publicbooleanisMatch(String s,String p){int sRight = s.length(), pRight = p.length();while(sRight >0&& pRight >0&& p.charAt(pRight -1)!='*'){if(charMatch(s.charAt(sRight -1), p.charAt(pRight -1))){--sRight;--pRight;}else{returnfalse;}}if(pRight ==0){return sRight ==0;}int sIndex =0, pIndex =0;int sRecord =-1, pRecord =-1;while(sIndex < sRight && pIndex < pRight){if(p.charAt(pIndex)=='*'){++pIndex;
                sRecord = sIndex;
                pRecord = pIndex;}elseif(charMatch(s.charAt(sIndex), p.charAt(pIndex))){++sIndex;++pIndex;}elseif(sRecord !=-1&& sRecord +1< sRight){++sRecord;
                sIndex = sRecord;
                pIndex = pRecord;}else{returnfalse;}}returnallStars(p, pIndex, pRight);}publicbooleanallStars(String str,int left,int right){for(int i = left; i < right;++i){if(str.charAt(i)!='*'){returnfalse;}}returntrue;}publicbooleancharMatch(char u,char v){return u == v || v =='?';}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~