Wildcard Matching

• Lintcode : 192 / Lintcode : 44
• Level : Hard

Problem

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

Example
Example 1

Input:
"aa"
"a"
Output: false
Example 2

Input:
"aa"
"aa"
Output: true
Example 3

Input:
"aaa"
"aa"
Output: false
Example 4

Input:
"aa"
"*"
Output: true
Explanation: '*' can replace any string
Example 5

Input:
"aa"
"a*"
Output: true
Example 6

Input:
"ab"
"?*"
Output: true
Explanation: '?' -> 'a' '*' -> 'b'
Example 7

Input:
"aab"
"c*a*b"
Output: false

Concept & Algorithm

筆記1
筆記2
筆記3

Time Complexity & Space Complexity

time : O()
space: O()

Answer

class Solution {
public:
    bool isMatch(string &s, string &p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> isVisited(n, vector<bool>(m, false));
        vector<vector<bool>> memo(n, vector<bool>(m, false));
        return dfs(s, p, 0, 0, isVisited, memo);
    }
private:
    bool dfs(string &s, string &p, int sIndex, int pIndex, vector<vector<bool>> &isVisited, vector<vector<bool>> &memo) {
        if (sIndex == s.size() && pIndex == p.size()) return true;
        if (pIndex == p.size()) return false;
        if (sIndex == s.size()) {
            for (int i = pIndex; i < p.size(); i++) 
                if (p[i] != '*') return false;
            return true;
        }
        if (isVisited[sIndex][pIndex]) return memo[sIndex][pIndex];
        bool normal = false, left = false, right = false;
        if (s[sIndex] == p[pIndex] || p[pIndex] == '?') {
            normal = dfs(s, p, sIndex + 1, pIndex + 1, isVisited, memo);
        }else if (p[pIndex] == '*') {
            left = dfs(s, p, sIndex + 1, pIndex, isVisited, memo);
            right = dfs(s, p, sIndex, pIndex + 1, isVisited, memo);
        }
        isVisited[sIndex][pIndex] = true;
        memo[sIndex][pIndex] = normal || left || right;
        return memo[sIndex][pIndex];
    }
};

tags: DP

​