【解题报告】【lintcode192】Wildcard Matching

题意

判断两个可能包含通配符“?”和“”的字符串是否匹配。匹配规则如下:
‘?’ 可以匹配任何单个字符。
‘ 可以匹配任意字符串(包括空字符串)。
两个串完全匹配才算匹配成功。
一些例子:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, ““) → true
isMatch(“aa”, “a
“) → true
isMatch(“ab”, “?“) → true
isMatch(“aab”, “c
a*b”) → false

解答

对于’?’的匹配很简单,直接忽略即可
对于’‘的匹配,找到这个符号时,记录它的位置和匹配串的位置,在下一次开始时从这个点后开始匹配,如果不匹配就在匹配串上面往后移一位
以上过程结束后,对于匹配串的遍历就结束了,如果模式串还有未遍历的部分,只能是

代码

u3coding
A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.