53 - 正则表达式匹配

前端之家收集整理的这篇文章主要介绍了53 - 正则表达式匹配前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目:

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

解析:
字符串 str = “aaa”; 模式字符串 pattern = “.b*ac*a”
每次分别在str 和pattern中取一个字符进行匹配,如果匹配,则匹配下一个字符,否则,返回不匹配。
设匹配递归函数 match(str,pattern)。

如果模式匹配字符的下一个字符是‘*’:

  • 如果pttern当前字符和str的当前字符匹配,:有以下三种可能情况
    • pttern当前字符能匹配 str 中的 0 个字符:match(str,pattern+2)
    • pttern当前字符能匹配 str 中的 1 个字符:match(str+1,pattern+2)
    • pttern当前字符能匹配 str 中的 多 个字符:match(str+1,pattern)
  • 如果pttern当前字符和和str的当前字符不匹配
    • pttern当前字符能匹配 str 中的 0 个字符:(str,pattern+2)

如果模式匹配字符的下一个字符不是‘*’,进行逐字符匹配。

对于 ‘.’ 的情况比较简单,’.’ 和一个字符匹配 match(str+1,pattern+1)
另外需要注意的是:空字符串”” 和 “.*” 是匹配的

bool MatchCore(const char* str,const char* pattern) {
    if (*str == '\0' && *pattern == '\0')
        return true;
    // if (*str == '\0' && *pattern != '\0') return false : 不成立,如str = "",pattern=".*"
    if (*str != '\0' && *pattern == '\0' )
        return false;

    if (*(pattern+1) == '*') {
        if (*pattern == *str || *pattern == '.' && *str != '\0') {
            //三种情况:*之前的字符出现 0 次,出现一次,出现多次. pattern+2表示跳过当前字符和‘*’
            return MatchCore(str,pattern+2) || MatchCore(str+1,pattern);
        } else {
            // 没有匹配,出现 0 次(包括str=“”,pattern=“.*”)
            return MatchCore(str,pattern+2);
        }
    }
    if (*str == *pattern || *pattern == '.' && *str != '\0')
        return MatchCore(str+1,pattern+1);
    return false;
}
bool Match(const char* str,const char* pattern) {
    if (pattern == NULL || str == NULL)
        return false;
    return MatchCore(str,pattern);
}

测试案例:
From:剑指offer源码 GitHub

// ==================== Test Code ====================

void Test(char* testName,char* string,char* pattern,bool expected)
{
    if(testName != NULL)
        printf("%s begins: ",testName);

    if(Match(string,pattern) == expected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}

int main(int argc,char* argv[])
{
    Test("Test01","",true);
    Test("Test02",".*",true);
    Test("Test03",".",false);
    Test("Test04","c*",true);
    Test("Test05","a",true);
    Test("Test06","a.",false);
    Test("Test07",false);
    Test("Test08",true);
    Test("Test09","ab*",true);
    Test("Test10","ab*a",false);
    Test("Test11","aa",true);
    Test("Test12","a*",true);
    Test("Test13",true);
    Test("Test14",false);
    Test("Test15","ab",true);
    Test("Test16",true);
    Test("Test17","aaa","aa*",true);
    Test("Test18","aa.a",false);
    Test("Test19","a.a",true);
    Test("Test20",".a",false);
    Test("Test21","a*a",true);
    Test("Test22",false);
    Test("Test23","ab*ac*a",true);
    Test("Test24","ab*a*c*a",true);
    Test("Test25",true);
    Test("Test26","aab","c*a*b",true);
    Test("Test27","aaca",true);
    Test("Test28","aaba",false);
    Test("Test29","bbbba",".*a*a",true);
    Test("Test30","bcbbabab",false);

    return 0;
}
@H_44_404@

猜你在找的正则表达式相关文章