j******4
发帖数: 116 | 1 记得版上提到过。就是简化啦的regex, 只考虑* 和 . 及a-z.
感觉要做nfs/dfs 转化等等对面试不现实。有大牛给指点一下吧。 |
d**e
发帖数: 6098 | 2 不知是不是前面说的string match ？
【在 j******4 的大作中提到】
: 记得版上提到过。就是简化啦的regex, 只考虑* 和 . 及a-z.
: 感觉要做nfs/dfs 转化等等对面试不现实。有大牛给指点一下吧。
|
j******4
发帖数: 116 | 3 不是啊。 那个是wildcard match, 一个loop 就可以了。
这个是 regex.
没人有兴趣？ 自己顶一下。 |
j*****g
发帖数: 223 | 4 好像没什么不同呀
regex limited to . and * 不就是wildcard matching? wildcard match一个loop就可
以吗？再想想看。。。 |
d**e
发帖数: 6098 | 5 应该是不一样。我估计他说的应该还包括
^$
[a-z]
[a|z]
{n,m}
{n,}
{n}
可能还有其它的
【在 j*****g 的大作中提到】
: 好像没什么不同呀
: regex limited to . and * 不就是wildcard matching? wildcard match一个loop就可
: 以吗？再想想看。。。
|
j*****g
发帖数: 223 | 6 well, then we need clarification.
^$
[a-z]
[x|y]
shouldn't be hard. More or less the same algorithm.
dealing {} my quick gut feeling is similar to deal with . or *.
could be wrong :)
【在 d**e 的大作中提到】
: 应该是不一样。我估计他说的应该还包括
: ^$
: [a-z]
: [a|z]
: {n,m}
: {n,}
: {n}
: 可能还有其它的
|
j******4
发帖数: 116 | 7 不一样啊不一样。。。再看看书？
ｒｅｇｅｘ 这个，网上有个很好的解，好像是在那个很慢的ｄｒ． ｄｕｂｂ站上。
刚搜啦一下找不到拉。但是很适合ｉｎｔｅｒｖｉｅｗ．
一般解这个可以借鉴：http://swtch.com/~rsc/regexp/regexp1.html 理解啦以后写下来也不难。不过这个文章大方向好像是错的。wiki 的解释比较中肯。。 |
M**u
发帖数: 10158 | 8 这个很容易啊
就让你给个表达式就可以了
【在 j******4 的大作中提到】
: 不一样啊不一样。。。再看看书？
: ｒｅｇｅｘ 这个，网上有个很好的解，好像是在那个很慢的ｄｒ． ｄｕｂｂ站上。
: 刚搜啦一下找不到拉。但是很适合ｉｎｔｅｒｖｉｅｗ．
: 一般解这个可以借鉴：http://swtch.com/~rsc/regexp/regexp1.html 理解啦以后写下来也不难。不过这个文章大方向好像是错的。wiki 的解释比较中肯。。
|
j******4
发帖数: 116 | 9 wildcard match一个loop就可
恩，说的不够细， main loop 有一个， 但是需要retract, 所以总的cost 应该是 O(
mn).
谢谢。 |
