leetcode 第43题 Wildcard Matching

时间:2022-09-01 20:47:28
题目:(这题好难。题目意思类似于第十题,只是这里的*就是可以匹配任意长度串,也就是第十题的‘.*’)
'?' 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") → false
题目的意思就不重复了如第十题,就是匹配的问题,这里的'?'相当于第十题的'.',匹配单一字符,这里的'*'相当如第十题的'.*'匹配任意长度的字符。所以是不是就想到可以用相同的递归方法就好了。
不行的,会超时,也算是熟悉了下递归思路吧。超时代码如下:
leetcode 第43题 Wildcard Matchingleetcode 第43题 Wildcard Matching
 1 class Solution {
 2 public:
 3     bool isMatch(const char *s, const char *p)
 4     {
 5         while(p + 1 != NULL && *(p+1) == *p && *p == '*') p++;
 6         if (*p == '\0')
 7             return *s == '\0';
 8         if (*s == *p || *p == '?' && *s != '\0')
 9             return isMatch(s + 1, p + 1);
10         else if (*p == '*')
11         {
12             if (*s == '\0')
13                 return isMatch(s, p + 1);
14             while(*s != '\0')
15             {
16                 if(isMatch(s, p + 1)) return true;
17                 s++;
18             }
19         }
20         return false;
21     }
22 };
View Code

其实这个动态规划也不那么好理解。看了半天才把这个人的代码看懂。我加了注释如下:

主要就是要弄清楚下标。他的下标有点乱,但又不得不那样。dp[lens + 1][lenp + 1]是因为还要存长度为0 和0的匹配,以及0和若干个*的匹配都是真值。

dp[j][i]的意思是,s的第1到j和p的第1到i是否匹配,也就是下标s的0到j-1的字符串和p的下标0到i-1的字符串是否匹配。

则:

if p[j] == '*' && (dp[i][j-1] || dp[i-1][j])  ------a

dp[i][j] =  1 

else p[j] = ? || p[j] == s[i]     -------b

dp[i][j] = dp[i-1][j-1];

else dp[i][j] = false;     --------c

class Solution {  
public:  
  
    bool isMatch(const char *s, const char *p) {  
        int len_s = strlen(s);  
        int len_p = strlen(p);  
  
        const char* tmp = p;  
        int cnt = 0;  
        while (*tmp != '\0') if (*(tmp++) != '*') cnt++;  
        if (cnt > len_s) return false;// 如果没有*的长度比待匹配的字符串还长是不可能匹配的,所以false  
          
        bool dp[len_s + 1][len_p + 1];  
        memset(dp, false,sizeof(dp));  
  
        dp[0][0] = true;  
        for (int i = 1; i <= len_p; i++) {  
            if (dp[0][i-1] && p[i-1] == '*') dp[0][i] = true; // p[i-1]是p的第i个,dp[][i-1]是到p的第i-1个
                                                        //所以如果p的前i-1个是*,并且第i个也是*的话,那么dp[0][i]就是真        
            for (int j = 1; j <= len_s; ++j)  
            {  
                if (p[i-1] == '*') dp[j][i] = (dp[j-1][i] || dp[j][i-1]); //注意下标就发现,对应上面博文中的注释------a  
                else if (p[i-1] == '?' || p[i-1] == s[j-1]) dp[j][i] = dp[j-1][i-1];  //对应博文中的------b
                else dp[j][i] = false;  //对应博文中的-------c
            }  
        }  
        return dp[len_s][len_p];  
    }  
};

还有一个是据说80ms过的。用贪心的。贴出如下:

class Solution {  
public:  
bool isMatch(const char *s, const char *p) {  
    // Start typing your C/C++ solution below  
    // DO NOT write int main() function  
    if(!s && !p) return true;  
  
    const char *star_p=NULL,*star_s=NULL;  
  
    while(*s)  
    {  
        if(*p == '?' || *p == *s)  
        {  
            ++p,++s;  
        }else if(*p == '*')  
        {  
            //skip all continuous '*'  
            while(*p == '*') ++p;  
  
            if(!*p) return true; //if end with '*', its match.  
  
            star_p = p; //store '*' pos for string and pattern  
            star_s = s;  
        }else if((!*p || *p != *s)  && star_p)  
        {  
            s = ++star_s; //skip non-match char of string, regard it matched in '*'  
            p = star_p; //pattern backtrace to later char of '*'  
        }else  
            return false;  
    }  
  
    //check if later part of p are all '*'  
    while(*p)  
        if(*p++ != '*')  
            return false;  
  
    return true;  
}  
};  

最后我想说,真TM难。。。