原題

判斷兩個(gè)可能包含通配符“？”和“*”的字符串是否匹配。匹配規(guī)則如下：

'?' 可以匹配任何單個(gè)字符。
'*' 可以匹配任意字符串（包括空字符串）。

兩個(gè)串完全匹配才算匹配成功。

函數(shù)接口如下:
bool isMatch(const char *s, const char *p)

一些例子：

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

解題思路

• 動(dòng)態(tài)規(guī)劃，內(nèi)存需要優(yōu)化，滾動(dòng)數(shù)組, 10000 * 10000 轉(zhuǎn)化成 2 * 10000
• 狀態(tài)cache[i][j]表示S的前i和T的前j是否match
• 狀態(tài)轉(zhuǎn)移
• 如果PD[i-1][j]==true或者PD[i][j-1]==true，并且s[i]=='*'或者p[j]=='*'時(shí)PD[i][j]==true；
• 如果PD[i-1][j-1]==true時(shí)，s[i]與p[j]匹配，則PD[i][j]==true。
• 換句話(huà)說(shuō)，一個(gè)格子的True或者False只與左側(cè)，左上和上方的格子有關(guān)，如下圖

Screenshot at Jun 05 04-37-09.png

完整代碼

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if len(p) - p.count('*') > len(s):   #avoid TLE(Time Limited Exceeded)
            return False
        cache = [[False for i in range(len(s) + 1)] for j in range(2)]
        cache[0][0] = True
        for j in range(1, len(p) + 1):
            cache[j % 2][0] = cache[(j - 1) % 2][0] and p[j - 1] == "*"
            for i in range(1, len(s) + 1):
                cache[j % 2][i] = False
                if s[i - 1] == p[j - 1] or s[i - 1] == "?" or p[j - 1] == "?":
                    cache[j % 2][i] = cache[(j - 1) % 2][i - 1]
                if s[i - 1] == "*" or p[j - 1] == "*":
                    cache[j % 2][i] = cache[(j - 1) % 2][i] or cache[j % 2][i - 1]
        return cache[len(p) % 2][len(s)]