1. 首页
  2. 剑指offer经典面试题

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

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

第 19 题:正则表达式匹配

传送门:正则表达式匹配牛客网 online judge 地址

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

模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含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。

liwei201910113_1.png

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

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

liwei201910111_2.png

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

采用递归的解题方法,递归的终止条件是:

1、如果 sp 都只有一个字符,相等的充要条件是,它们相等,或者 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. 正则表达式匹配,难度是:困难

使用动态规划:

liwei20191018_3.png

dp 函数这么写。

liwei20191017_4.png

思路:当字符串只有一个字符时,直接进行判断,否则进入下面两种递归。

两种递归情况:1、当模式中的第二个字符不是 * 时:

(1)如果字符串第一个字符和模式中的第一个字符相匹配或是字符 . 那么字符串和模式都后移一个字符,然后匹配剩余 的;

(2)如果字符串第一个字符和模式中的第一个字符相不匹配,直接返回 false

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

如果“字符串”第一个字符跟“模式串”第一个字符不匹配,则模式后移 2 个字符,继续匹配;

如果“字符串”第一个字符跟“模式串”第一个字符匹配或是字符 . ,可以有 3 种匹配方式:

(1)模式后移 2 字符,相当于 x 被忽略;

(2)字符串后移 1 字符,模式后移 2 字符;

(3)字符串后移 1 字符,模式不变,即继续匹配字符下一位,因为可以匹配多位。

liwei20191016_5.png

liwei20191016_6.png

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3268.html

« [剑指 Offer 第 2 版第 18 题] “删除链表中重复的结点”做题记录
[剑指 Offer 第 2 版第 20 题] “表示数值的字符串”做题记录»

相关推荐

QR code