- #刷题
[Leetcode]花半年解决Wildcard Matching 而且还是用Python另附完整Java
Linzertorte643716
找工作的时候刷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
最后的几行就是小贪心一下。
最后的最后是我的提交记录。真的半年啦
类似的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
最后的几行就是小贪心一下。
最后的最后是我的提交记录。真的半年啦
