Leetcode skimming ---44

subject ： Given a string  (s) And a character pattern  (p) , Implement a support  '?'  and  '*'  The wildcard matches .

• '?' It can match any single character .
• '*' Can match any string （ Include empty string ）.

Only when two strings match exactly can the match be successful .

explain :

• s  May is empty , And contains only from  a-z  Lowercase letters of .
• p  May is empty , And contains only from  a-z  Lowercase letters of , As well as the character  ?  and  *.

Input ：s = "aa" ,p = "a"

Output ：false

Method 1 ： Dynamic programming

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

Complexity analysis

Time complexity ：O(mn)

Spatial complexity ：O(mn)

Method 2 ： Greedy Algorithm

class Solution {
public:
    bool isMatch(string s, string p) {
        auto allStars = [](const string& str, int left, int right) {
            for (int i = left; i < right; ++i) {
                if (str[i] != '*') {
                    return false;
                }
            }
            return true;
        };
        auto charMatch = [](char u, char v) {
            return u == v || v == '?';
        };
        while (s.size() && p.size() && p.back() != '*') {
            if (charMatch(s.back(), p.back())) {
                s.pop_back();
                p.pop_back();
            } else {
                return false;
            }
        }
        if (p.empty()) {
            return s.empty();
        }
        int sIndex = 0, pIndex = 0;
        int sRecord = -1, pRecord = -1;
        while (sIndex < s.size() && pIndex < p.size()) {
            if (p[pIndex] == '*') {
                ++pIndex;
                sRecord = sIndex;
                pRecord = pIndex;
            } else if (charMatch(s[sIndex], p[pIndex])) {
                ++sIndex;
                ++pIndex;
            } else if (sRecord != -1 && sRecord + 1 < s.size()) {
                ++sRecord;
                sIndex = sRecord;
                pIndex = pRecord;
            } else {
                return false;
            }
        }
        return allStars(p, pIndex, p.size());
    }
};

Complexity analysis

Time complexity ：O(mn)

Spatial complexity ：O(mlogn)