剑指offer - 正则表达式匹配

题目

请实现一个函数用来匹配包含.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串aaa与模式a.a和ab*ac*a匹配，但与aa.a和ab*a均不匹配。

• aaa与a.a相匹配，那是因为.表示任意一个字符，即当.为a时，两个字符串自然相等，匹配传给。
• aaa与ab*ac*a匹配，那是因为*表示它前面的字符可以出现任意次（含0次），即当字符串ab*ac*a中*前面的字符出现0次时，ab*ac*a正好为aaa
• aa.a和ab*a很显然是不匹配的

思路

总的思路：每次从字符串里拿出一个字符和模式中的字符去匹配

1、当模式中的第二个字符不是*时

• 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
• 如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。

2、当模式中的第二个字符是*时

如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
如果字符串第一个字符跟模式第一个字符匹配，可以有2种匹配方式：

• 字符串后移1字符，模式后移2字符(相当于*被忽略)；
• 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；

具体例子分析

如何匹配一个字符：如果模式中的字符ch是'.'，那么它可以匹配字符串中的任意字符。如果模式中的字符ch不是'.'，而且字符串中的字符也是ch，那么它们相互匹配。当字符串中的字符和模式中的字符相匹配时，接着匹配后面的字符

当模式中的第二个字符不是*时，问题要简单很多。如果字符串中的第一个字符和模式中的第一个字符相匹配，那么在字符串和模式上都后移一个字符，然后匹配剩余的字符串和模式。如果字符串中的第一个字符和模式中的第一个字符不相匹配，则直接返回false

当模式中的第二个字符是*时，问题要复杂一些，因为可能有多种不同的匹配方式。一种选择是在模式上向后移动两个字符。这相当于*和它前面的字符被忽略了，因为*可以匹配字符串的0个字符。

如果模式中的第一个字符和字符串中的第一个字符相匹配，则在字符串上后移一个字符，而在模式上有两种选择：可以在模式上向后移动两个字符，也可以保持模式不变

如下图，当匹配进入状态2并且字符串的字符是'a'时，我们有两种选择：可以进入状态3（在模式上向后移动两个字符），也可以回到状态2（模式保持不变）

download.jpg

算法实现

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

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
            return matchCore(str, pattern + 2); // 忽略*
    }

    // 如果当前字符的下一个字符不是*，并且字符相等，或者当字符串未结束的情况下，模式字符为.，那么当前字符匹配成功，进行下一个字符匹配
    if (*str == *pattern || (*pattern == '.' && *str != '\0'))
        return matchCore(str + 1, pattern + 1);

    return false;
}

参考

《剑指offer》