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

找工作的时候刷leetcode,主要用C++刷了140题。但是Wildcard matching死活过不了。
类似的regular expression matching用回溯过了。
然后今天受到一个启发用Non-deterministic automata来做。一个bit_vector表示当前状态。
然后这个NFA也很好构造。如果对应位置有个*,说明有一个自环。如果是字母或者?,有一个走向下一状态的边。
代码倒是好写。

首先这题如果有连续有*.那么只保留一个即可。
这个复杂度为O(m*n) m 是len(s), n是len(p)



然后发就Time limited exceed在之前C++就通不过那个长长的"aaaaaaaaaaaaaaaaaaaaaaaaa..."上。然后就以为是因为他有许多"aaaa",然后pattern是一个aaaa*所以过了不。
然后就想到一个优化。把pattern分解成三个部分 第一部分与第三部分都没有*
left,middle, right
比如pattern=abc*daf?*dsaf*?df
left=abc
middle = *daf?*dsaf*
right = ?df

我们定义match_from(i,s,p)  即一个不含*，可能含有?的pattern p可以match s[i..i+len(pattern)-1]
然后还是超时。

不过这个将pattern分成三部分的想法又给了我一个启发。

其实我们完全可以将这个pattern按照*来split.得到的chunks都不含有*

然后这题要求exact match
所以第一个chunk和最后一个chunk必须与s的开头和结尾match



剩下的就是中间的chunks,还有那个去头去尾的s,如果称去头去尾的s为s'

我们接下来的match就可以采取信心的策略。

上面为s',下面就是chunks.
没有arrow指向的s'中字母我们一律用*来match

每个chunk我们只需要尽可能靠左去match.这个不会影响结果。而且这个性质很容易证明。

开始让begin=0
然后发现   match_from(begin,'aaa',s') ==True  
这样aaa match就match上了。
我们让begin += len('aaa')
begin现在是3.
即从3开始match第二个chunk bbc
直到begin==11的时候match_from(begin,'bbc',s')==True
我们又完成了第二个chunk的match..
..如此如此so on and so forth.
然后下面是代码

这一大段主要是用来对s进行掐头去尾。。许多corner case

最后的几行就是小贪心一下。

最后的最后是我的提交记录。真的半年啦

https://github.com/Linzertorte/L ... WildcardMatching.py
Python最终版。只在30行。

这题G onsite考到了，我当时写的是：

    bool isMatch(const char *s, const char *p)
    {
        const char* star_pos = 0;
        const char* s_pos = 0;
        
        while(*s != '\0')
        {
           if(*s == *p || *p == '?') //一对一的match
           {
               s++;
               p++;
               continue;
           }
           if(*p == '*') //很多'*'连在一起和一个'*'效果是一样的
           {
               star_pos = p;
               p++;
               s_pos = s;
               continue;
           }
           if(star_pos != 0)
           {
               s = s_pos++; //s_pos的作用是如果s和p在第一个if里不能匹配到底（即p到底s还没到底），s可以重新回到s_pos
                            //s_pos++后重新开始匹配相当于'*'又多消灭s中的一个字符
               p = star_pos+1; //p重新回到star_pos+1
               continue;
           }
           return false; //如果上面三个if都进不去，s又还没到头，那么匹配失败
        }
        while(*p == '*') p++; //忽略剩下的'*'
        return *p == '\0';
    }

这里附上另外整理的Java代码。

厉害

当初用java写的，调了一个晚上才过了，一开始用DP超时，后来改用贪心+KMP才过了

ralf 发表于 2014-7-10 21:54
这题G onsite考到了，我当时写的是：

    bool isMatch(const char *s, const char *p)

幸亏我G onsite没面这题。要不然我就挂了。

pyemma 发表于 2014-7-10 20:57
当初用java写的，调了一个晚上才过了，一开始用DP超时，后来改用贪心+KMP才过了

KMP点赞。

Linzertorte 发表于 2014-7-11 02:38
KMP点赞。

理解了KMP，写带？的KMP就很简单了

pyemma 发表于 2014-7-11 11:24
理解了KMP，写带？的KMP就很简单了

这倒也是。计算next指针的时候比如p[i]==?或者p[i]==s[j]都算是匹配成功。