44. Wildcard Matching (Hard) Google Facebook Twitter Snapchat TwoSigma

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

外卡匹配和正则匹配最大的区别就是在星号的使用规则上，对于正则匹配来说，星号不能单独存在，前面必须要有一个字符，而星号存在的意义就是表明前面这个字符的个数可以是任意个，包括0个，那么就是说即使前面这个字符并没有在s中出现过也无所谓，只要后面的能匹配上就可以了。而外卡匹配就不是这样的，外卡匹配中的星号跟前面的字符没有半毛钱关系，如果前面的字符没有匹配上，那么直接返回false了，根本不用管星号。而星号存在的作用是可以表示任意的字符串，当然只是当匹配字符串缺少一些字符的时候起作用，当匹配字符串包含目标字符串没有的字符时，将无法成功匹配。

Solution 1: 同向Two Pointers O(m * n); O(1)

    /**
     * 同向Two Pointers O(m * n); O(1)
     * 1.advancing both pointers when (both characters match) or ('?' found in pattern)
     * 2.* found in pattern, track index of *, only advancing pattern pointer
     * 3.current characters didn't match, last pattern pointer was *, current pattern pointer is not *, 
     * only advancing pattern pointer
     * 4.current pattern pointer is not star, last patter pointer was not *, characters do not match
     * 5.check for remaining characters in pattern
     */
    public boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        int match = 0;
        int star = -1;
        while (i < s.length()) {
            if (j < p.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
                j++;
                i++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                star = j;
                match = i;
                j++;
            } else if (star != -1) {
                j = star + 1;
                match++;
                i = match;
            } else {
                return false;
            }
        }

        while (j < p.length() && p.charAt(j) == '*') {
            j++;
        }
        return j == p.length();
    }

Solution 2: DP O(m * n); O(m * n)

    public boolean isMatchB(String s, String p) {
        if (s == null || p == null) {
            return false;
        }

        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = true;
            } else {
                break; // Pruning. If found 1 mismatch, the following won't match.
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if (p.charAt(j - 1) == '*') {
            //'*' matches empty or '*' matches s[i-1], 这种情况时，一个'*'最后可能匹配从s.charAt(j - 1)开始的很多个字符。
            //这样就用到了'*'(向后匹配)匹配多个字符的功能，所以如果写成dp[i - 1][j - 1]，那么只用到了'*'匹配一个字符的功能。
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; // dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1]; //wrong
                }
            }
        }
        return dp[m][n];
    }

Solution 3: DP O(m * n); O(m)

    /**
     * DP O(m * n); O(m)
     * use pre to replace dp[i - 1][j - 1]
     */
    public boolean isMatchC(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[] dp = new boolean[m + 1];
        dp[0] = true;
        for (int j = 1; j <= n; j++) {
            boolean pre = dp[0];
            dp[0] = dp[0] && p.charAt(j - 1) == '*';
            for (int i = 1; i <= m; i++) {
                boolean temp = dp[i];
                if (p.charAt(j - 1) != '*') {
                    dp[i] = pre && (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?');
                } else {
                    dp[i] = dp[i - 1] || dp[i];
                }
                pre = temp;
            }
        }
        return dp[m];
    }