频道栏目
首页 > 资讯 > 其他 > 正文

Wildcard Matching:通配符匹配的实现

17-12-13        来源:[db:作者]  
收藏   我要投稿

Implement wildcard pattern matching with support for'?'and'*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
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
思路:最大的难点在于:

ab|ef|cd|g|i|esc|de
ab|* |cd|?|i|*|de

这种匹配,即一个*不知道要匹配多少个字符,可能先匹配一个字符满足要求,但是后来的匹配过程中发现无法继续匹配时,需要回到*位置,匹配两个字符,再继续向前匹配,不断重复,直到匹配完全或者发现不能匹配。因此,对于每个*位置,需要记录下*的位置以及当时匹配的状态情况(类似于游戏中的复活点,可以saveloading)。

代码参考的Leetcode讨论区的高票答案。

class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0;//尝试匹配 s
        int j = 0;//尝试匹配 p
        int resurgence = -1;//匹配失败时的复活点,即因为*的出现可能有多种长度的匹配,所以其中一种失败后
        //p从“复活点”(上一个出现*的位置的状态)重新匹配,而s在复活点处对应的字符则可以由*匹配,即更换成另一种长度的匹配
        
        int mark = 0;//记录下匹配到*时s对应的位置,用于“复活”(用*将s的当前字符串匹配掉)
        
        while(i

 

 

 

相关TAG标签
上一篇:nodejs express4.X框架不支持layout模板的问题如何解决?
下一篇:JS和Jquery获取和修改label的值的代码教程
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站