首页 > 其他 > 详细

[LeetCode] #44 Wildcard Matching

时间:2015-06-18 00:32:46      阅读:384      评论:0      收藏:0      [点我收藏+]

mplement 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

本题是匹配问题,如果遇到‘?’就匹配任意一个字符,如果是‘*’,匹配0-n个字符。利用贪心算法求解。时间:20ms。代码如下:
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) 
            return s.empty();
        string::const_iterator pter = p.begin(), ster = s.begin();
        string::const_iterator star_p, star_s;
        bool sign = false;
        while (ster!=s.end()){
            if (pter == p.end()){
                if (sign){
                    ster = ++star_s;
                    pter = star_p;
                }
                else
                    break;
            }
            else if (*pter == ? || *pter == *ster)
                ++pter, ++ster;
            else if (*pter == *){
                while (pter != p.end() && (*pter == * || *pter == ?)){
                    if (*pter == ?){
                        ++pter;
                        ++ster;
                        if (ster == s.end())
                            break;
                    }
                    else
                        ++pter;
                }
                if (pter==p.end()) 
                    return true;
                star_p = pter;
                star_s = ster;
                sign = true;
            }
            else if ((*pter != *ster || *pter!=?) && sign){
                ster = ++star_s;
                pter = star_p; 
            }
            else
                return false;
        }
        if (ster != s.end())
            return false;
        while (pter!=p.end())
            if (*pter++ != *)
                return false;
        return true;
    }
};

 

[LeetCode] #44 Wildcard Matching

原文:http://www.cnblogs.com/Scorpio989/p/4584571.html

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