Wildcard Matching

Problem: Wildcard Matching'

The problem is quite similar to regular expression matching. However, the online judge requires less running time and extra space, which means we need to implement early return and one-dimension dynamic programming.

Code in Python:

class Solution(object):
    def isMatch(self, s, p):
        m,n=len(s),len(p)
        if n-p.count('*')>m:   #avoid TLE
            return False
        dp=[False]*(n+1)
        for i in xrange(m+1):
            pre=dp[0]
            dp[0]= (i==0)
            for j in xrange(1,n+1):
                temp=dp[j]
                dp[j]=(pre or dp[j] or dp[j-1]) if p[j-1]=='*' else (pre and (p[j-1]=='?' or s[i-1]==p[j-1]))
                pre=temp
        return dp[n]

Code in Java:

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        for (int i = 1; i < m+1; i++) dp[i][0] = false;
        for (int i = 1; i < n+1; i++) {
            if (dp[0][i-1] == true && p.charAt(i-1) == '*') dp[0][i] = true;
            else dp[0][i] = false;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i-1][j-1] == true && s.charAt(i-1) == p.charAt(j-1)) dp[i][j] = true;
                else if (dp[i-1][j] == true && p.charAt(j-1) == '*') dp[i][j] = true;
                else if (dp[i][j-1] == true && p.charAt(j-1) == '*') dp[i][j] = true;
                else if (dp[i-1][j-1] == true && p.charAt(j-1) == '*') dp[i][j] = true;
                else if (dp[i-1][j-1] == true && p.charAt(j-1) == '?') dp[i][j] = true;
                else dp[i][j] = false;
            }
        }

        return dp[m][n];
    }
}