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", "cab") → false

https://leetcode.com/problems/wildcard-matching/

Solution I: adopt from Regular Expression Matching, TLE

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.length() == 0 && p.length() == 0) {
            return true;
        }    

        if (p.length() == 0) {
            return false;
        }

        if (p.length() == 1) {
            if (s.length() == 0 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '?')) {
                return false;
            }
            if (p.charAt(0) == '*') {
                return true;
            }
            return isMatch(s.substring(1), p.substring(1));
        }

        char c = p.charAt(1);

        if (c != '*') {
            if (s.length() == 0 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '?')) {
                return false;
            }

            return isMatch(s.substring(1), p.substring(1));
        } else {
            if (isMatch(s, p.substring(2))) {
                return true;
            }

            int i = 0;

            while (i < s.length()) {
                if (isMatch(s.substring(i+1), p.substring(2))) {
                    return true;
                }
                i++;
            }

            return false;
        }
    }
}

Solution II: DP (2D)

https://leetcode.com/discuss/66038/java-solution-o-n-2-dp-solution-with-some-explanations

public class Solution {
    public boolean isMatch(String s, String p) {

    if(p.length()==0)
        return s.length()==0;

    boolean[][] res = new boolean[p.length()+1][s.length()+1];

    res[0][0] = true;

    for (int i = 1; i <= p.length(); i++) {
        boolean flag = false;
        for (int j = 0; j <= s.length(); j++) { // note that j starts from 0
            char c = p.charAt(i-1);
            flag = flag || res[i-1][j];

            if (c != '*') {
                res[i][j] = j>0 && res[i-1][j-1] && (c == '?' || s.charAt(j-1) == c);
            } else {
                // For k>=0 and k<=j, if any dp[i-1][k] is true,
                // then '*' will match the rest sequence in s after index k;
                res[i][j] = i==1 || flag; // note that if i == 1 && c == '*', then res[1][j] = true
            }
        }
    }

    return res[p.length()][s.length()];

    }
}

Solution III: DP(1D)

http://blog.csdn.net/linhuanmars/article/details/21198049

public class Solution {
    public boolean isMatch(String s, String p) {
    if(p.length()==0)
        return s.length()==0;
    boolean[] res = new boolean[s.length()+1];
    res[0] = true;
    for(int j=0;j<p.length();j++)
    {
        if(p.charAt(j)!='*')
        {
            for(int i=s.length()-1;i>=0;i--)
            {
                res[i+1] = res[i]&&(p.charAt(j)=='?'||s.charAt(i)==p.charAt(j));
            }
        }
        else
        {
            int i = 0;
            while(i<=s.length() && !res[i])
                i++;
            for(;i<=s.length();i++)
            {
                res[i] = true;
            }
        }
        res[0] = res[0]&&p.charAt(j)=='*';
    }
    return res[s.length()];
}
}