LeetCode 44. Wildcard Matching [Hard] [C++] 解題筆記

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 *.

注意這裡的 '*' 是匹配任意字串!

EX:

    Input:

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

想法:

    這題可以用 DP 的方式求解，我們可以假設 dp[i][j] 代表 s[0:i-1] 與 p[0:j-1] 是否可以匹配，因此 

dp[i][j] = dp[i - 1][j - 1] && ((s[i - 1] == p[j - 1]) || p[j - 1] == '?'

         || dp[i - 1][j] && p[j - 1] == '*' ('*'可以匹配任意字串，因此這裡'*'匹配 s[i])

         || dp[i][j - 1] && p[j - 1] == '*' ('*'可以匹配認識字串，因此這裡'*'匹配 空字串)

另外這題我們可以使用兩個一維陣列來實作DP以節省空間，因為從遞迴式中可以觀察到我們只需要紀錄前一列與當前列的結果即可。

完整程式碼:

Complexity: O(nm) time, O(nm) space. n is len of s, m is len of p

解法一:

//dp[i][j] means that s from 0~i and p from 0~j match or not

class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
        // empty pattern match empty string
        dp[0][0] = true;
        bool p_empty = false;
        for (int i = 1; i <= s.size(); i++) {
            dp[i][0] = (dp[i-1][0] && p_empty);
        }
        for (int j = 1; j <= p.size(); j++) {
            dp[0][j] = (dp[0][j-1] && p[j-1] == '*');
        }
        
         
        //return false;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= p.size(); j++) {
                dp[i][j] = (dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?')) || (dp[i-1][j] && p[j-1] == '*') || (dp[i][j-1] && p[j-1] == '*');
            }
        }/*
        for (int i = 0; i <= s.size(); i++) {
            for (int j = 0; j <= p.size(); j++) {
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }*/
        return dp[s.size()][p.size()];
    }
};

解法二(space optimization):

Complexity: O(nm) time, O(m) space. n is len of s, m is len of p

class Solution {
public:
    bool isMatch(string s, string p) {
        // empty pattern match empty string
        
        vector<bool> pre(p.size() + 1, false);
        vector<bool> cur(p.size() + 1, false);
        pre[0] = true;
        bool p_empty = false;
        
        for (int j = 1; j < pre.size(); j++) {
            pre[j] = pre[j-1] && p[j-1] == '*';
        }
        
        cur = pre;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j <= p.size(); j++) {
                if (j == 0) { 
                    cur[j] = pre[j] && p_empty; 
                }
                else {
                    cur[j] = (pre[j-1] && (s[i-1] == p[j-1] || p[j-1] == '?')) || (pre[j] && p[j-1] == '*') || (cur[j-1] && p[j-1] == '*');
                }
            }
            pre = cur;
        }
        
        return cur[p.size()];
    }
};