Day 79, #44, Wildcard Matching

Wildcard 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

---------------------------------------------------------------
Solution #1 recursion, OJ time limit exceeded

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') {
            return *s == '\0';
        }
        
        if (*p == *s || *p == '?') {
            return isMatch(s + 1, p + 1);
        }
        
        if (*p == '*') {
            while (*s != '\0') {
                if(isMatch(s,p + 1)) {
                    return true;
                }
                s++;
            }
        }
        
        return false;
    }
};

Solution #2, dp with 2d arrays,

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

改良版DP，用了一个一维数组，当*p == '*',dp[j]只取决于dp[j - 1]，过不了最后一个test case

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

Solution #3, constant space
star用来记录最近*的位置，index用来记录当前*匹配成功后s的位置。*之前全部匹配成功，不用再重复检测。*之后如果匹配失败，回头从star + 1 和 index重新匹配，每匹配失败一次，index增加一位。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char *star = NULL;
        const char *index = s;
        
        while (*s != '\0') {
            if (*s == *p || *p == '?') {
                s++;
                p++;
            }else if (*p == '*') {
                star = p;
                p++;
                index = s;
            }else if (star != NULL) {
                p = star + 1;
                index++;
                s = index;
            }else return false;
        }
        
        while (*p == '*') {
            p++;
        }
        
        return *p == '\0';
    }
};

Java,2维dp

class Solution {
    public boolean isMatch(String s, String p) {
        List<List<Boolean>> dp = getDP(s, p);
            
        for (int i = 0; i < p.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (dp.get(i).get(j) && (s.charAt(j) == p.charAt(i) || p.charAt(i) == '?')) {
                    dp.get(i + 1).set(j + 1, true);
                } else if (p.charAt(i) == '*' && (dp.get(i).get(j + 1) || dp.get(i + 1).get(j))) {
                    dp.get(i + 1).set(j + 1, true);
                }
            }
        }
        
        return dp.get(p.length()).get(s.length());
    }
    
    private List<List<Boolean>> getDP(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<List<Boolean>> dp = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            List<Boolean> inner = new ArrayList<>();
            if (i == 0 || (i > 0 && dp.get(i - 1).get(0) && p.charAt(i - 1) == '*')) inner.add(true);
            else inner.add(false);
            for (int j = 0; j < m; j++) {
                inner.add(false);
            }
            dp.add(inner);
        }
        
        return dp;

    }
}