JZ19 正则表达式匹配

描述

请实现一个函数用来匹配包括’.’和’*’的正则表达式。

1.模式中的字符’.’表示任意一个字符

2.模式中的字符’*’表示它前面的字符可以出现任意次（包含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配

数据范围:

• $str$ 只包含从 a-z 的小写字母。
• pattern 只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘‘。
• $0≤str.length≤26 $
• $0≤pattern.length≤26 $

示例1

输入："aaa","a*a"
返回值：true
说明：中间的*可以出现任意次的a，所以可以出现1次a，能匹配上

示例2

输入："aad","c*a*d"
返回值：true
说明：因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。

示例3

输入："a",".*"
返回值：true
说明：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）

示例4

输入："aaab","a*a*a*c"
返回值：false

题解

用一个指针$si$指向$str$当前被匹配的位置，然后去遍历$pattern$，其中每一个字符有三种情况

• 当前字符是普通字母，直接比较，$si$向后挪一次。
• 当前字符是$’*’$，对比字符左侧的字母，考虑$si$向后挪零次还是多次。
• 当前字符是$’.’$，对比字符左侧的字母，$si$向后挪一次。

当处理$’*’$时

• 如果左侧的字母不匹配，那么$si$不动
• 如果匹配的话，匹配零次或者多次。

边界条件：空字符串和空模式：二者都空则成功，只有一个空则不匹配。

实际上来说，就是以下三种情况：

• 普通匹配：普通字母或者$’.’$进行匹配，前者需要比较，后者不需要比较，都是一个字符与一个字符进行匹配。
• $’‘$匹配情况一：字母的下一个字符是$’‘$，且该次视为匹配零次，$si$不动，$pi+2$跳过该字符和$’*’$，不需要考虑字母是否匹配的情况。
• $’‘$匹配情况二：字母的下一个字符是$’‘$，且该次视为匹配一次或多次，$si+1$，$pi$不动，需要考虑字母匹配的情况。

判断这三种情况进行递归，可以探索到所有的情况。

代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param pattern string字符串
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        return isMatch(str, pattern, 0, 0);
    }
  private:
    bool isMatch(const string& s, const string& p, int si, int pi) {
        // 如果模式已经遍历完，并且字符串也遍历完，则匹配成功
        if (si == s.length() && pi == p.length()) return true;

        // 如果模式遍历完，字符串没有遍历完，匹配失败
        if (pi == p.length()) return false;

        // 如果当前字符是'.'，或者字符相同，则可以继续匹配
        bool match = (si < s.length()) && (p[pi] == s[si] || p[pi] == '.');

        // 处理 '*'，有两种情况：
        if (pi + 1 < p.length() && p[pi + 1] == '*') {
            // 1. * 前面的字符匹配0次：跳过当前字符和 '*'，直接继续匹配
            if (isMatch(s, p, si, pi + 2)) return true;
            // 2. * 前面的字符匹配1次或多次：如果当前字符匹配，则继续匹配字符串
            if (match && isMatch(s, p, si + 1, pi)) return true;
        } else {
            // 如果没有 '*'，则普通字符匹配
            if (match && isMatch(s, p, si + 1, pi + 1)) return true;
        }

        return false;
    }

};