正则表达式匹配

发布时间：2020-12-14 05:35:24 所属栏目：百科来源：网络整理

导读：【问题】请实现一个函数用来匹配包括‘.‘和‘ ‘的正则表达式。模式中的字符‘.‘表示任意一个字符，而‘ ‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab ac a"匹配，

【问题】请实现一个函数用来匹配包括‘.‘和‘‘的正则表达式。模式中的字符‘.‘表示任意一个字符，而‘‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。

【思路】

首先我们先使用递归的方法，既然要写递归程序，首先考虑递归的退出条件，第一，如果str和pattern都遍历结束到了‘‘，返回true.第二，如果str没有遍历完，而pattern遍历结束了，则不匹配，返回false。第三，str遍历完了，但pattern没有完，可能存在‘*‘，需要进行处理，否则返回false.

假如第二个字符是‘*‘，那么分为两种情况：

如果第一个字符和pattern匹配成功（注意‘.‘的情况），那么下一步分成三个情况：
1.‘x* ‘匹配到一个字符，因此str+1,pattern+2
2.‘x* ‘匹配到多个字符，需要重复判断，因此str+1,pattern不变
3.‘x* ‘匹配到0个字符，str不动，因此，str,pattern+2

?
如果第一个字符和pattern不匹配，直接跳过‘x*‘,pattern+2即可！

其他情况，如果两个字符匹配，str和pattern均向后移动，str+1,pattern+1.

class Solution {
public:
    bool match(char* str,char* pattern){
        if(str == nullptr || pattern == nullptr){
            return false;
        }
        return matchCore(str,pattern);
    }
private:
    bool matchCore(char* str,char* pattern){
        if(*str == ‘‘ && *pattern == ‘‘){
            return true;
        }
        if(*str != ‘‘ && *pattern == ‘‘){
            return false;
        }
        if(*(pattern+1) == ‘*‘){   // 当前字符的下一个字符是‘*‘
            if(*str == *pattern || (*pattern == ‘.‘ && *str != ‘‘)){
                return matchCore(str+1,pattern+2) ||
                    matchCore(str+1,pattern) ||
                    matchCore(str,pattern+2);
            }else{
                return matchCore(str,pattern+2);
            }
        }
        if(*str == *pattern || (*pattern == ‘.‘ && *str != ‘‘)){
            return matchCore(str+1,pattern+1);
        }
        return false;
    }
};

（编辑：李大同）

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