Wildcard Matching

通配符匹配问题，这道题实在没想到是一个纯DP问题，而且解决的方式非常简单，虽然逻辑上面有点绕，其实仔细观察，很容易发现一个问题，问号这个符号实际上代表的意思和一个纯字母的pattern区别不大，下面的代码也体现了，所以实际上最难用逻辑描述的部分就是星号的部分了，当然星号也是正则表达式里功能最强大的符号之一，此题因为是通配符，所以星号单独一个字母就可以替代从0到无限长的任意字符，其实意识到这一点后，就可以将星号单独分为三种情况讨论，一是星号的匹配不用，二是星号用来匹配一个字符，三是星号用来匹配多于一个字符，其实到这里就可以看出这道题实际上就跟LCS非常像了， 字符相等的情况不用多说，星号的情况也只是有三种不同而已，以dp[i][j]为例，当当前s[i]等于p[j]时，直接找dp[i-1][j-1]，问号时情况也一样，这里把状态方程简单写下

if s[i] == p[j] or p[j] == '*'
    dp[i][j] = dp[i - 1][j - 1]
else
    dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j]

上面else里面的三种情况分别对应通配符匹配0个，匹配一个，匹配多个的情况

通过上面的状态方程也很容易看出来逻辑如何实现了，另外对于正则表达式匹配的这两道题，矩阵的初始化还有一些特殊的地方，例如这道题的话，左边缘部分除了dp[0][0]都是False，但是上边缘需要初始化，初始化的规则在代码里，口述说不太清

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        n = len(s)
        m = len(p)

        dp = [([False] * (m + 1)) for _ in xrange(n + 1)]
        dp[0][0] = True
        for i in xrange(1, m + 1):
            dp[0][i] = (dp[0][i - 1] and p[i - 1] == '*')

        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = (dp[i - 1][j] or dp[i][j - 1] or dp[i - 1][j - 1])

        return dp[n][m]

此题还有一个贪心算法可以解（时间复杂度和DP是一个量级的，可能只是常数项比较小而已），解题思路比较复杂，可以参考两篇博客：LeetCode: Wildcard Matching 解题报告，http://www.programcreek.com/2014/06/leetcode-wildcard-matching-java/

下面是代码

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        n, m = len(s), len(p)
        indexS, indexP = 0, 0
        starIndex, strIndex = -1, -1

        while indexS < n:
            if indexP < m and (p[indexP] == '?' or p[indexP] == s[indexS]):
                indexP += 1
                indexS += 1
            elif indexP < m and p[indexP] == '*':
                starIndex = indexP
                strIndex = indexS
                indexP += 1
            elif starIndex != -1:
                indexP = starIndex + 1
                indexS = strIndex + 1
                strIndex += 1
            else:
                return False

        while indexP < m and p[indexP] == '*':
            indexP += 1
        return indexP == m