登录
  • #刷题

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

Linzertorte
6437
16
找工作的时候刷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



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

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

16条回复
热度排序

发表回复