正则表达式匹配

---

题目描述

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

解题思路

通过给出的例子可以看出：当匹配的当前字符相等或者匹配字符是'.'时，直接将字符串和匹配字符串进行下一位匹配；否则直接返回false.

但是若当匹配的字符为'*'时就比较麻烦：

若匹配的下一个字符为'*'时，可以分为以下几种情况：

• 字符串中当前字符与匹配字符串中当前字符相等，或者匹配字符串中当前字符为'.'时，又会有以下几种情况

  • 当'*'前面的字符出现0次时，字符串中的字符保持当前位与匹配字符串中字符后移两位比较，matchCore（str, pattern + 2 ）
  • 当'*'前面的字符出现1次时，字符串中的字符后移一位与匹配字符串中字符后移两位(跳过'*')比较，matchCore(str + 1, pattern + 2)
  • 当'*'前面的字符出现2次以上时，字符串中的字符后移一位与匹配字符串中当前字符比较，matchCore(str + 1, pattern)

• 字符串中当前字符与匹配字符串中当前字符不相等，则直接比较字符串中的当前字符与匹配字符串中字符后移两位(跳过'*')，matchCore(str, pattern + 2)

若字符串当前字符与匹配字符串的当前字符相等，或者匹配字符串的当前字符是'.'

• 字符串中的字符后移一位与匹配字符串中字符后移两位(跳过'*')比较，matchCore(str + 1, pattern + 2)

代码

class Solution
{
public:
    bool match (char* str, char* pattern)
    {
        if (str == NULL || pattern == NULL)
            return false;
        return matchCore(str, pattern);
    }
    
    bool matchCore (char* str, char* pattern)
    {
        if (*str == '\0' && *pattern == '\0') // 若两个字符同时结束则返回true
            return true;
        if (*str != '\0' && *pattern == '\0') // 若匹配字符串先结束，则返回false
            return false;
        // 下一个字符为 '*'
        if (*(pattern + 1) == '*')
        {
            if (*str == *pattern || (*pattern == '.' && *str != '\0'))
                return (matchCore(str, pattern + 2)) || (matchCore(str + 1, pattern + 2)) || (matchCore(str + 1, pattern));
            else
                return matchCore(str, pattern + 2);
        }
        
        // 当前字符相等，或匹配字符为 '.'
        if (*str == *pattern || (*pattern == '.' && *str != '\0'))
            return matchCore(str + 1, pattern + 1);
        return false;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_52.html