[剑指 Offer 第 2 版第 19 题] “正则表达式匹配”做题记录

第 19 题：正则表达式匹配

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

模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

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

样例：

``` 输入：

s="aa" p="a*"

输出:true ```

思路：这题考察的是动态规划。笔记我写在这里了：《剑指 Offer》（第 2 版）第 19 题：正则表达式匹配。

Python 代码：

  class Solution(object):

        # 状态：dp[i][j] 表示 s 中前 i 个字符与 p 的前 j 个字符组成的表示式是否匹配
        # i 和 j 表示个数
        # 代码中出现 i 均表示 s 中的索引或者个数
        # 代码中出现 j 均表示 p 中的索引或者个数
        # 出现 -1 都表示当前考虑的
        # 出现 -2 都表示当前再前一个

        # 参考资料：http://www.voidcn.com/article/p-zioiffqq-mm.html

        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            n = len(s)
            m = len(p)

            dp = [[False for _ in range(m + 1)] for _ in range(n + 1)]

            # 当 s 和 p 的长度都为 0 的时候，定义成匹配
            dp[0][0] = True

            # 特判
            for j in range(2, m + 1):
                if p[j - 1] == '*' and dp[0][j - 2]:
                    dp[0][j] = True

            # 下面分别对字符串 s 和模式串 p 进行匹配
            for i in range(1, n + 1):
                for j in range(1, m + 1):

                    if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                        dp[i][j] = dp[i - 1][j - 1]
                    elif p[j - 1] == '*':
                        # 这是最麻烦的情况

                        if p[j - 2] != s[i - 1] and p[j - 2] != '.':
                            # 例子：s a
                            #        j-1
                            #      p b    *
                            #        j-2  j-1
                            # 此时只能把 * 当成 0 次，即 * 和它之前的字母不出现，所以一下子要减去 2
                            # p[j - 2] != '.' 这一点别忘了
                            # 不能匹配
                            dp[i][j] = dp[i][j - 2]
                        else:
                            # 接下来是可以匹配
                            # 例子：s a
                            #        j-1
                            #      p .    *
                            #        j-2  j-1
                            # 此时把 * 当成 0 次，
                            # 此时把 * 当成 1 次，
                            # 此时把 * 当成 多 次，直接把 i - 1 ，这是最难的地方
                            dp[i][j] = dp[i][j - 2] or dp[i][j - 1] or dp[i - 1][j]
            return dp[n][m]

方法2：递归的写法。

参考资料：一个网红的解法：http://www.cnblogs.com/grandyang/p/4461713.html。有解法 1 还有解法2。

网红写法：https://blog.csdn.net/hk2291976/article/details/51165010

说明：这个网红还写了 leetbook。

参考资料：https://zhuanlan.zhihu.com/p/37647267。

采用递归的解题方法，递归的终止条件是：

1、如果 $s$ 和 $p$ 都只有一个字符，相等的充要条件是，它们相等，或者 $p$ 是 '.'；

其他递归情况：

1、如果 $p$ 的第二个字符不是 '*'，那么如果 $s$ 是空，返回 false，如果 $s[0]$ 和 $p[0]$ 能匹配上，那么递归 s.substr(1), p.substr(1)；

==坏就坏在，如果 $p$ 的第二个字符是 '*'==。

2、如果 $p$ 的第二个字符是 ‘*’，因为我们知道 ‘‘ 可以代表 ‘‘ 之前的元素个数是 $0$ 个或者 $1$ 个或者多个，所以如果 $s$ 的前 $k$ 个元素个 $p[0]$ 一样，那么它们有可能都被匹配到，也有可能一个都不会被匹配上。

C++ 写法：

  class Solution {
    public:
        bool isMatch(string s, string p) {
            if(p.empty())return s.empty();
            if(p.size() == 1) {
                 return(s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
            }

            if(p[1] != '*')  {
                if(s.empty())return false;
                return (s[0] == p[0] || p[0] == '.')&& isMatch(s.substr(1), p.substr(1));
            }
            // 走到这里 p[1] == '*'，下面的 4 行代表比较难理解
            while(!s.empty() && (s[0] == p[0] || p[0] == '.')) {
                if(isMatch(s, p.substr(2))) return true;
                s = s.substr(1);
            }
            return isMatch(s, p.substr(2));
        }
    };

要求：请实现一个函数用来匹配包括 . 和 * 的正则表达式。模式中的字符 . 表示任意一个字符，而 * 表示它前面的字符可以出现任意次，包括 $0$ 次。

LeetCode 第 10 题，传送门：10. 正则表达式匹配，难度是：困难。

使用动态规划：