lintcode 通配符匹配 ac代码

发布时间：2020-12-14 06:47:20 所属栏目：百科来源：网络整理

导读：今天在lintcode看到一道题，看了一下午的答案都没看懂，深深的挫败感，先记录下来，日后在啃实现支持 '.' 和 '*' 的正则表达式匹配。 '.'匹配任意一个字母。 '*'匹配零个或者多个前面的元素。匹配应该覆盖整个输入字符串，而不仅仅是一部分。需要实现的

今天在lintcode看到一道题，看了一下午的答案都没看懂，深深的挫败感，先记录下来，日后在啃

实现支持'.'和'*'的正则表达式匹配。

'.'匹配任意一个字母。

'*'匹配零个或者多个前面的元素。

匹配应该覆盖整个输入字符串，而不仅仅是一部分。

需要实现的函数是：bool isMatch(const char *s,const char *p)

您在真实的面试中是否遇到过这个题？

Yes

样例

isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa","a*") → true

isMatch("aa",".*") → true

isMatch("ab",".*") → true

isMatch("aab","c*a*b") → true

2017/9/1号更新，今天又看了一遍，看懂了一些，这种做法属于动态规划，主线分为当前字母之后的一个字母是*和不是*的两种情况，并且整体风格是递归的向后检测匹配与否，每一个环节只用考虑当前的情况是否匹配，实在是一个好方法

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
    bool isMatch(const char *s,const char *p) {
        // write your code here
        if(*p == '')
            return *s == '';
 
        if(*(p+1) != '*'){
            if((*p == '.' && *s != '') || *p == *s){//*s如果为结束符即使*p为.当前也不匹配
                return isMatch(s+1,p+1);
            }else{
                return false;
            }
        }else{
            while((*p == '.' && *s != '') || *p == *s){
                if(isMatch(s,p+2))//每个遇到*号都可以先把它跳过匹配后面的
                    return true;
                s++;//match one more *
            }
            return isMatch(s,p+2); //这是当前两个字符不相等，寻找*后的字符与s是否相等的情况
        }
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!