首页 > 其他 > 详细

Wildcard Matching

时间:2014-07-11 19:35:55      阅读:421      评论:0      收藏:0      [点我收藏+]
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

思路:通配符匹配与Regular Expression Matching都是相似的题型。当s[i]==p[j]或者p[j]==‘?‘即匹配,则i++,j++;如果p[j]==‘*‘,则记录此时*的位置以及s[i]的位置,从*的下一个位置匹配,开始匹配。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char *star=NULL;
        const char *curs=NULL;
        while(*s!=\0)
        {
            if(*s==*p||*p==?)
            {
                s++;
                p++;
                continue;
            }
            if(*p==*)
            {
                star=p;
                p++;
                curs=s;
                continue;
            }
            if(star!=NULL)
            {
                p=star+1;
                s=curs+1;
                curs++;
                continue;
            }
            return false;
        }
        while(*p==*)
            p++;
        return *p==\0;
    }
};

 

 

Wildcard Matching,布布扣,bubuko.com

Wildcard Matching

原文:http://www.cnblogs.com/awy-blog/p/3833564.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!