[Leetcode]花半年解决Wildcard Matching 而且还是用Python另附完整Java

Linzertorte 发表于 2014-7-11 12:37
这倒也是。计算next指针的时候比如p==?或者p==s[j]都算是匹配成功。

是的

Linzertorte 发表于 2014-7-11 12:37
这倒也是。计算next指针的时候比如p==?或者p==s[j]都算是匹配成功。

不过我还是被python的超短code惊异到了，我用Java足足写了100行！

这题是LC最难过的一道了 谢谢lz分享！

仔细看了，真是相当nb的解法！

当时做regular 匹配的时候TLE，我直接把pattern 缩减了下。。举例，'aaa*' -> 'aa*'（匹配的字符串是一样的，后者表达能力更强。。）
做这道题参考了Yu 的思路，记录*的思路实在太漂亮了。
AC过了，我的代码：
    def isMatch(self, s, p):
        len_s, len_p = len(s), len(p)
        pPointer=sPointer=0
        star = -1
        while sPointer < len_s:
            if pPointer >= len_p:
                if star != -1:
                    sPointer, pPointer = star
                    sPointer +=1
                    continue
                else:
                    return False
            if p[pPointer] == "?" or p[pPointer]==s[sPointer]:
                pPointer+=1
                sPointer+=1
            elif p[pPointer] == '*':
                star = (sPointer,pPointer)
                pPointer+=1
            else:
                if star != -1:
                    sPointer, pPointer = star
                    sPointer +=1
                else:
                    return False

        if pPointer < len_p:
            while pPointer < len_p and p[pPointer]=='*':
                pPointer+=1

        return True if pPointer == len_p else False

怎么感觉像是AC自动机？

austurela 发表于 2014-10-22 11:01
这题是LC最难过的一道了 谢谢lz分享！

一般一般。