列表

详情


NC44. 通配符匹配

描述

请实现支持'?'and'*'.的通配符模式匹配
'?' 可以匹配任何单个字符。
'*' 可以匹配任何字符序列(包括空序列)。
返回两个字符串是否匹配
函数声明为:
bool isMatch(const char *s, const char *p) 
只有p字符串包含通配符
下面给出一些样例:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "d*a*b") → false
数据范围:字符串长度满足
进阶:空间复杂度 ,时间复杂度

示例1

输入:

"ab","?*"

输出:

true

示例2

输入:

"ab","*"

输出:

true

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 2ms, 内存消耗: 396KB, 提交时间: 2021-06-05

#include <stdbool.h>
/**
 * 
 * @param s string字符串 
 * @param p string字符串 
 * @return bool布尔型
 */
bool isMatch(char* s, char* p ) {
    // write code here
    char *s_record = NULL, *p_record;
    while( *s )
    {
        if( *p ){
            if(*p==*s || *p=='?'){ p++;   s++;   continue; }
            if(*p == '*'){ p_record = ++p;   s_record = s;   continue; }
        }
        if( s_record ){ s = ++s_record;   p = p_record;   continue; }
        return false;
    }
    while(*p && *p=='*') p++;
    return !*p;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2021-09-14

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s), n = strlen(p);
        int i = 0, j = 0, star = -1; // i, j为遍历两个字符串的指针,star指向"*"字符
        int match = 0; // 记录上次未匹配的位置
        while (i < m) {
            if (s[i] == p[j] || p[j] == '?') { // 若当前位置s字符串与p字符串字符相同,或当前p字符串的字符为"?"
                i++;
                j++;
            } 
            else if (p[j] == '*') { // 当前p字符串的字符为"*"
                star = j;
                match = i; // 更新match
                j++;
            } 
            else {
                if (star >= 0) { // 前面的位置有"*"
                    j = star + 1;
                    match++;
                    i = match;
                }
                else // 未匹配成功,且之前没有"*"
                    return false;
            }
        }
        while (j < n) { // p长度较长,则必须全为"*"
            if (p[j] != '*')
                return false;
            j++;
        }
        return true;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2021-09-11

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s), n = strlen(p);
        int i = 0, j = 0, star = -1; // i, j为遍历两个字符串的指针,star指向"*"字符
        int match = 0; // 记录上次未匹配的位置
        while (i < m) {
            if (s[i] == p[j] || p[j] == '?') { // 若当前位置s字符串与p字符串字符相同,或当前p字符串的字符为"?"
                i ++;
                j ++;
            } else if (p[j] == '*') { // 当前p字符串的字符为"*"
                star = j;
                match = i; // 更新match
                j ++;
            } else {
                if (star >= 0) { // 前面的位置有"*"
                    j = star + 1;
                    match ++;
                    i = match;
                }
                else // 未匹配成功,且之前没有"*"
                    return false;
            }
        }
        while (j < n) { // p长度较长,则必须全为"*"
            if (p[j] != '*')
                return false;
            j ++;
        }
        return true;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 532KB, 提交时间: 2021-07-27

class Solution {
public:
    bool res = true;
//     bool dfs(const char *s, int sIndex, const char *p, int pIndex)
//     {
//         if(strlen(s)<=sIndex&&strlen(p)<=pIndex)
            
//         if (pIndex<strlen(p)&&p[pIndex]=='?')
            
//     }
    bool isMatch2(const char *s, const char *p) {
        const char* star=NULL;
        const char* ss=s;
        while (*s){
            // 当(两个字符匹配)或(模式串的字符为'?')时,将两个指针同时前进一步
            // 注意p不会超出字符串的长度
            if ((*p=='?')||(*p==*s)){s++;p++;continue;}
            // 模式串的字符为'*'时,记录'*'的位置与s的位置,并且只让模式串的指针前进一步
            if (*p=='*'){star=p++; ss=s;continue;}
            // 如果当前字符不匹配,最后一个指针是'*',当前模式指针非'*'
            // 只让模式串的指针前进一步
            if (star){ p = star+1; s=++ss;continue;}
            // 当前模式指针指向非'*',最后一个模式串指针非'*',且字符不匹配
            return false;
        }
 
        // 检查模式中剩余字符
        while (*p=='*'){p++;}
 
        return !*p;
    }
    
    
    
    
    
    
    
    
    
    bool isMatch(const char *s, const char *p)
    {
        const char *star = nullptr;
        const char *ss = nullptr;
        while(*s!='\0')
        {
            if (*p=='?' || *s==*p)
            {
                p++;
                s++;
                continue;
            }
            if (*p=='*')
            {
                star = p++;
                ss = s;
                continue;
            }
            
            if(star)
            {
                p=star+1;
                s=++ss;
                continue;
            }
            return false;
        }
        // 检查模式中剩余字符
        while (*p=='*'){p++;}
 
        return !*p;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 540KB, 提交时间: 2021-09-09

class Solution {
public:
    //动态规划打表
    bool isMatch(const char *s, const char *p) {
      vector<vector<bool> > x(strlen(s)+1,vector<bool>(strlen(p)+1,0));
      x[0][0]=true;
      int i=1;
      while(p[i-1]=='*') x[0][i]=true,i++;
      for(int i=1;i<=strlen(s);i++)
        for(int j=1;j<=strlen(p);j++)
           if(p[j-1]=='*')
           {
               bool flag=0;
               for(int k=i-1;k>=0;k--)
                 if(x[k][j]) {flag=1;break;}
               if(flag||x[i][j-1]) x[i][j]=1;
           }
           else if(p[j-1]=='?')
               x[i][j]=x[i-1][j-1];
           else
               x[i][j]=(s[i-1]==p[j-1] ? x[i-1][j-1]:false);
      return x[strlen(s)][strlen(p)];
    }
};

上一题