本文主要是介绍044 - Wildcard Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).The function prototype should be:
bool isMatch(const char *s, const char *p)Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → falsechar *mystrstr(char *src, char *dst)
{int slen = strlen(src);int len = strlen(dst);char *a = src;char *b = dst;int cnt = 0, i;while (slen >= len) {b = dst;a = src + cnt;for (i = 0; i < len; i++) if (a[i] != b[i] && b[i] != '?') break;if (i == len) return src + cnt;slen--;cnt++;}return NULL;
}int dofun(char *s, char **pword, int pcnt, int begin, int end)
{if (pcnt < 1) return (begin || end || !*s)? 1:0;char *out = mystrstr(s, pword[0]);int pw0 = strlen(pword[0]);if (pcnt == 1) {if (!out) return 0;if (begin)return (end || mystrstr(s + strlen(s) - pw0, pword[0]))? 1:0;else return ((end && out == s) || (out == s && !out[pw0]))? 1:0;}char *ss = s;int cur = 0;if (!begin) {if (out != s) return 0;cur ++;ss += pw0;}if (!end) {int sslen = strlen(ss);int plen = strlen(pword[pcnt - 1]);if (sslen < plen) return 0;if (!mystrstr(ss + sslen - plen, pword[pcnt - 1]))return 0;char *t = s + strlen(s) - plen;*t = '\0';pcnt--;}for (; cur < pcnt; cur++) {out = mystrstr(ss, pword[cur]);int plen = strlen(pword[cur]);if (!out) return 0;ss = out + plen;}return 1;
}int isMatch(char* s, char* p)
{int i, ret, begin, end, wcnt = 0;char *pword[2048] = {0};char *pw;/* split string by char '*' */begin = end = 0;if (*p == '*') begin = 1;if (p[strlen(p) - 1] == '*') end = 1;pw = strtok(p, "*");while (pw) {int pwlen = strlen(pw);pword[wcnt] = (char *)malloc(sizeof(char) * (pwlen + 1));memcpy(pword[wcnt++], pw, pwlen + 1);pw = strtok(NULL, "*"); }ret = dofun(s, pword, wcnt, begin, end);for (i = 0; i < wcnt; i++) free(pword[i]);return ret;
}
这篇关于044 - Wildcard Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
