offer150-19:正则表达式匹配

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

分析：每次从字符串里拿一个字符和模式中的字符去匹配。如果模式中的字符是 '.' ,那么它可以匹配字符串中的任意一个字符。如果模式中的字符不是 '.' ,而有具体的某个字符，且与字符串中的当前字符相同，那么它们相互匹配。当字符串中的字符和模式中的字符相互匹配时，接着匹配后面的字符。

        当模式中的第二个字符不是' * '时，只要比较字符串中的第一个字符是否和模式中的第一个字符相匹配，如果相匹配，那么字符串和模式上都向后移动一个字符，如果不匹配，则直接返回false。

        当模式中的第二个字符是' * '时，需分类讨论。因为可能有多种不同的匹配方式。一种选择是' * '表示0次选择时，需要在模式上向后移动两个字符，这相当于' * '和它前面的字符被忽略了。第二种选择是当模式中的第一个字符和字符串中的第一个字符相匹配，则在字符串上向后移动一个字符，而在模式上又有两种选择：可以在模式上向后移动两个字符(表示已匹配完成)，也可以保持不变(表示未匹配完成,还需匹配)。

代码:

        

bool match(char* str,char* pattern){

    if(str == nullptr || pattern == nullptr){
        return false;
    }
    return matchCore(str,pattern);
}

bool matchCore(char* str,char* pattern){

    if(*str == '\0' && *pattern == '\0'){
        return true;
    }
    if(*str != '\0' && *pattern == '\0'){
        return false;
    }
    if(*(pattern + 1) == '*'){
        if(*pattern == *str || (*pattern == '.' && *str != '\0')){
            //如果第一个字符相匹配，且模式第二个字符是'*'
            return matchCore(str + 1,pattern + 2) || matchCore(str + 1,pattern) || matchCore(str,pattern + 2);
        }
        else {
            如果第一个字符不匹配，则该字符模式匹配0次，然后继续匹配下一个模式。
            return macthCore(str,pattern + 2);
        }
    }
    if(*str == *pattern || (*pattern == '.' && *str != '\0'){ //如果第二个字符不为'*',且第一个字符匹配
        return matchCore(str + 1,pattern + 1);         //继续匹配下一个字符
    }
    return false;                   //如果不匹配 则返回false
}

 

原文地址：https://blog.csdn.net/qq_31165949/article/details/140170813

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！