NC44. 通配符匹配
描述
请实现支持'?'and'*'.的通配符模式匹配'?' 可以匹配任何单个字符。返回两个字符串是否匹配
'*' 可以匹配任何字符序列(包括空序列)。
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)]; } };