首页 > 代码库 > leetcode. Wildcard Matching

leetcode. Wildcard Matching

2024-08-02 09:49:17   217人阅读

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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false

对于字符串匹配的问题，首先想到的是动态规划，用数组A[j][i]表示p[j]和s[i]的匹配情况,难点是*号的匹配。
1、如果p[j] != ‘*‘, 那么只要p[j] = s[i] 或者 p[j] = ‘?‘。
2、如果p[j] = ‘*‘, 则要看p[j-1]与s[k] 0<=k<=i有没有匹配，假设k匹配，则p[k]与s[k,...,i]全部匹配。
 1  bool isMatch(const char *s, const char *p)  2     { 3         int i, j; 4         if (!s || !p)    return false; 5  6         int m = strlen(p); 7         int n = strlen(s); 8         if (m == 0 || n == 0) 9                 return false;10 11         char **tb = new char*[m + 1];12         for (i = 0; i <= m; i++)13             tb[i] = new char[n + 1];14 15         tb[0][0] = true;16         for (j = 0; j < m; j++)17         {18             if (p[j] != ‘*‘)19             {20                 for (i = 0; i < n; i++)21                     tb[j + 1][i + 1] = tb[j][i] && (p[j] == ‘?‘ || p[j] == s[i]); 22             }23             else24             {25                 i = 0;26                 while ((i < n) && (tb[j][i] == false))27                     i++;28                 for (; i < n; i++)29                     tb[j + 1][i + 1] = true;30             }31         }32 33         return tb[m][n];34     }

时间复杂度O(mn), 空间复杂度O(mn)，运行出现Memory Limit Exceed。

在网上看到可以用贪心算法：

1、如果p[j] = s[i] 或者 p[j] = ‘?‘，继续下一次匹配。

2、否则，如果p[j] = ‘*‘,记录出现‘*‘的位置star和s当前的位置cs，p++;

3、如果1,2都不满足，说明出现不匹配，那么p回到star的位置继续匹配，相当于用‘*‘来匹配1中没有match的情况。

4、不满足1,2,3, 说明匹配失败。

    bool isMatch(const char *s, const char *p)     {        const char *star = NULL, *ss = s;        while (*s)        {            if(*p == ‘?‘ || *p == *s)            {                s++;                p++;            }            else if(*p == ‘*‘)            {                star = p++;                ss = s;            }            else if(star)            {                p = star + 1;                s = ++ss;            }            else            {                    return false;            }        }        while (*p == ‘*‘) p++;                return (*p == NULL);    }

 

leetcode. Wildcard Matching


联系
我们