Leetcode 44 Wildcard matching (2022.02.13)

  Given a string (s) And a character pattern § , 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 *.

Example 1:

Input :
s = “aa”
p = “a”
Output : false
explain : “a” Can't match “aa” Whole string .

Example 2:

Input :
s = “aa”
p = ""
Output : true
explain : '’ Can match any string .

Example 3:

Input :
s = “cb”
p = “?a”
Output : false
explain : ‘?’ Can match ‘c’, But the second one ‘a’ Can't match ‘b’.

Example 4:

Input :
s = “adceb”
p = “ab”
Output : true
explain : first ‘’ Can match an empty string , the second '’ Can match string “dce”.
Example 5:

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/wildcard-matching

Method 1 ： Dynamic programming

C++ Submission ：

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];
    }
};