写了DP的做法居然Memory Limit Exceeded了, 看了Yu Zhu的这个解法, O(N), 太犀利了! 遇到'*'时, 用star变量记录'*'在p中出现的位置, 用ss变量记录此时s字符串指针sPointer的位置, 但不移动sPointer, 因为'*'可以匹配0个字符, ss表示这个'*'所能匹配到的位置。遇到不匹配的情况时, 即走到if star!= -1时, pPointer被拉回到star的下一个位置, sPointer被拉回到ss的下一个位置, 继续匹配。把s字符串走完, p中还可以剩下一堆'*', 如果p中还有其他字符就返回False了。

class Solution:
    # @param s, an input string
    # @param p, a pattern string
    # @return a boolean
    def isMatch(self, s, p):
        len_s = len(s); len_p = len(p)
        pPointer = sPointer = ss = 0
        star = -1
        while sPointer < len_s:
            if pPointer < len_p and (p[pPointer] == '?' or p[pPointer] == s[sPointer]):
                sPointer += 1; pPointer += 1;
                continue
            if pPointer < len_p and p[pPointer] == '*':
                star = pPointer; pPointer +=1; ss = sPointer
                continue
            if star != -1:
                pPointer = star + 1; ss += 1; sPointer = ss
                continue
            return False
        while pPointer < len_p and p[pPointer] == '*':
            pPointer += 1
        return pPointer == len_p