[leetcode] Wildcard Matching

最大的疑惑在于不使用递归, 而又有多个*号出现时的回溯重试问题。

看起来如果第二次遇到*号时覆盖上次遇到*号时记录的重试位置,但是实际上第二个星号之前的匹配已经可以保证成功了,并且更重要的是这时上个星号匹配了多少字符已经无关了, 第二个星号可以吃掉多出来的字符。

比如下面这个例子

aababaababab
a*ab*ab

pattern中第一个*ab是匹配的哪个ab并不重要(只要不是最后一个就行,一般匹配第一个遇见的就好了),因为第二个*会吃掉多余的ab, 并且保证pattern中最后一个ab能够“够”到字符串的结尾。

此条目发表在 leetcode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>