[leetcode] wild card 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") → false

Copy

The wildcard matching problem of this problem is still a little difficult , Greedy algorithm is used in this road Greedy Alogrithm To solve , Because of the special characters * and ？, among ？ Can replace any character ,* Can replace any string , Then we need to define several additional pointers , among scur and pcur Respectively point to the currently traversed characters , Redefine pstar Point to p Last of * The location of ,sstar Point to the corresponding s The location of , The specific algorithm is as follows ：

– Definition scur, pcur, sstar, pstar

– If *scur There is

– If *scur be equal to *pcur perhaps *pcur by ‘?’, be scur and pcur All increase by themselves 1

– If *pcur by ’*’, be pstar Point to pcur Location ,pcur Self increasing 1, And sstar Point to scur

– If pstar There is , be pcur Point to pstar Next position of ,scur Point to sstar Self increasing 1 The back position

– If pcur by ’*’, be pcur Self increasing 1

– if *pcur There is , return False, If it does not exist , return True

C Solution 1 ：

bool isMatch(char *s, char *p) {
    char *scur = s, *pcur = p, *sstar = NULL, *pstar = NULL;
    while (*scur) {
        if (*scur == *pcur || *pcur == '?') {
            ++scur;
            ++pcur;
        } else if (*pcur == '*') {
            pstar = pcur++;
            sstar = scur;
        } else if (pstar) {
            pcur = pstar + 1;
            scur = ++sstar;
        } else return false;
    } 
    while (*pcur == '*') ++pcur;
    return !*pcur;
}

Copy

This problem can also be solved by dynamic programming Dynamic Programming To solve , The writing method is the same as the previous question Regular Expression Matching It's like , But it's still different . The biggest difference between wild card matching and regular matching is in the rules of using asterisks , For regular matching , The asterisk cannot exist alone , It must be preceded by a character , The meaning of the asterisk is to indicate that the number of characters in front of it can be any , Include 0 individual , That is to say, even if the previous character is not in s It doesn't matter if it appears in , As long as the latter can match . This is not the case with external card matching , The asterisk in the wild card matching has nothing to do with the previous character , If the preceding characters do not match , Then go straight back false 了 , Never mind the asterisk . The function of the asterisk is to represent any string , Of course, it only works when the matching string is missing some characters , When the matching string contains characters that the target string does not , Will not match successfully .

C++ Solution 2 ：

class Solution {
public:
    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];
    }
};

Copy

Similar topics ：

Regular Expression Matching

Reference material ：

https://discuss.leetcode.com/topic/3040/linear-runtime-and-constant-space-solution

https://discuss.leetcode.com/topic/40118/clear-c-dp-solution-similar-to-the-last-matching-problem

LeetCode All in One Summary of topic explanation ( Ongoing update …)

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/109497.html Link to the original text ：https://javaforall.cn