44_wildcard_matching.py

class Solution:
    # @param s, an input string
    # @param p, a pattern string
    # @return a boolean
    def isMatch(self, s, p):
        s_len = len(s)
        p_len = len(p)
        dp = [[None for j in xrange(p_len + 1)] for i in xrange(2)]
        # init
        dp[0][0] = True
        # when p is an empty string
        dp[1][0] = False
        # when s is an empty string
        for i in xrange(1, p_len + 1):
            dp[0][i] = dp[0][i - 1] and p[i - 1] == '*'
        # dp programming
        for i in xrange(1, s_len + 1):
            mod_i = i % 2
            mod_i_minus_1 = (i - 1) % 2
            for j in xrange(1, p_len + 1):
                ch = p[j - 1]
                if ch == '?':
                    dp[mod_i][j] = dp[mod_i_minus_1][j - 1]
                elif ch == '*':
                    # For * char, either matches the current character or nothing
                    dp[mod_i][j] = dp[mod_i_minus_1][j] or dp[mod_i][j - 1]
                else:
                    dp[mod_i][j] = dp[mod_i_minus_1][j - 1] if ch == s[i - 1] else False
        return dp[s_len % 2][p_len]