44. Wildcard Matching

This problem is simliar to 10. Regular Expression Matching. The difference lies in how the * works. In the previous problem, * can only matches zero or more of its preceding element. In this problem, * can match any sequence (including empty sequence). Of course, both the problems can be solved with DP, and the key is how we process *. In the previous problem, a* can be decoded as zero a, one a or more a. Similarly, in this problem, * can be decoded as empty sequence, one character or more character. Here, we use a two demension array to denote whether substrings of s and p match. match[i][j] denotes whether s.substring(0, i) and p.substring(0, j) matches. If p.charAt(j) is not *, we judge whether p.charAt(j) and s.charAt(i) matches. If p.charAt(j) is *, then there could be three conditions:

1. match[i][j] = match[i][j - 1], i.e., * is decoded as empty sequence
2. match[i][j] = match[i - 1][j - 1], i.e., * is decoded as one character
3. match[i][j] = match[i - 1][j], i.e., * is decoded as more than one character

public boolean isMatch(String s, String p) {
    boolean match[][] = new boolean[s.length() + 1][p.length() + 1];
    match[0][0] = true;
    for (int i = 0; i < p.length(); i++) // judge whether the substring of p matches empty sequence
	if (p.charAt(i) == '*')
	    match[0][i + 1] = match[0][i];
	for (int i = 0; i < s.length(); i++)
	    for (int j = 0; j < p.length(); j++) {
		if( p.charAt(j) == '*' )
		    match[i + 1][j + 1] = (match[i][j + 1] | match[i + 1][j] | match[i][j]);
		else if( s.charAt(i) == p.charAt(j) || p.charAt(j) == '?' )
		    match[i + 1][j + 1] = match[i][j];
	   }
    return match[s.length()][p.length()];
}