44. Wildcard Matching 通配符匹配

Given an input string (s) and a pattern (p), 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).

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

Difficulty: Hard

这道题和之前的第十题有点像.

这道里用了贪婪算法Greedy Alogrithm来解,由于有特殊字符*

?能替代任何字符,*能替代任何字符串.

解法1

bool isMatch(string s,string p){
    
    char *ss = new char[s.size()+1];
    strcpy(ss,s.c_str());
    char *pp = new char[p.size()+1];
    strcpy(pp,p.c_str());
    return isMatch2(ss,pp);
    
}

bool isMatch2(char *s, char *p) {
    
    /*
     scur,pcur 指向当前匹配的字符
     sstar 指向连续*中最后的一个位置
     pstar 指向此时s的位置
     */
    char *scur = s, *pcur = p, *sstar = NULL, *pstar = NULL;
    while (*scur) {
        // 如果当前字符匹配 则向后进行
        if (*scur == *pcur || *pcur == '?') {
            ++scur;
            ++pcur;
        }
        // 如果pcur指向*,则将pcur指向下一个(可能有连续的*),并记录当前的sstar为上一次scur
        else if (*pcur == '*') {
            pstar = pcur++;
            sstar = scur;
        }
        // 如果之前有遇到过*,取到当前的pcur,和scur
        else if (pstar) {
            pcur = pstar + 1;
            scur = ++sstar;
        }
        else {
            return false;
        }
    }
    while (*pcur == '*') ++pcur;
    return !*pcur;
}

解法2

采用dp的方法

bool isMatch(string s, string p) {
        int m = s.size(),n = p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        dp[0][0] = true;
        for (int i=1;i<=n;i++){
            if (p[i-1]=='*') dp[0][i] = dp[0][i-1];
        }
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                if (p[j-1]=='*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }else{
                    dp[i][j] = (s[i-1]==p[j-1]||p[j-1]=='?') && dp[i-1][j-1];
                }
            }
        }
        
        return dp[m][n];
    }

参考资料:

http://www.cnblogs.com/grandyang/p/4401196.html

 
comments powered by Disqus