剑指Offer(52)-- 正则表达式匹配(递归实现和动态规划)

题目描述

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

示例1
输入

“aaa”,“a*a”

返回值

true

思路以及解答

这道题,仔细一想,感觉情况很多,很凌乱,此处介绍的是递归的做法,其实本题还可以使用动态规划。最重要的是需要分类讨论,原串定义为str,模式串为pattern。`

  • 如果pattern长度为0
    • str长度为0,说明刚刚好匹配完,返回ture
    • str长度不为0,说明没有匹配完,返回false
  • 如果pattern的长度大于0
    • 分为两种情况讨论,一种是直接把**前面的字符去掉,相当于匹配了0个,然后接着比较;另外一种是,如果str的长度大于0,并且第一个字符匹配,那就把str的第一个字符去掉,两者接着匹配。
    • 如果pattern的长度大于1,且第2个字符是*,说明前面的字符可以匹配01或者多次
    • 否则,说明第二个字符不是*,那么就直接比较第一个字符是不是匹配,同时将后面的字符进行匹配。

注意:上面说的第一个字符是不是匹配,除了两个字符相等的情况,其实还有模式串的字符为’.'的情况。

    public boolean match(String str, String pattern) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        // 第二个字符是'*'
        if (pattern.length() > 1 && pattern.charAt(1) == '*') {
            // 匹配0次,直接把'*'去掉,两者判断
            return match(str, pattern.substring(2))
                    // 第一个字符相同的时候,去掉第一个字符,判断后面的(相当于匹配多次)
                    || (str.length() > 0 && firstSame(str, pattern)) && match(str.substring(1), pattern);
        } else {
            // 第二个字符不是 '*'的时候,判断第1个字符是否相同,相同的时候再从第2位开始比较
            return str.length() > 0 
                    && firstSame(str, pattern) 
                    && (match(str.substring(1), pattern.substring(1)));
        }
    }

    // 判断第一个字符是不是相同
    private boolean firstSame(String s, String p) {
        // 两个相同,或者有一个是"."
        return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
    }

当然,这种做法不是最优的,使用了大量的递归操作,并且重复递归,时间复杂度比较高。

当然,这道题还有一个更优的做法,但是过程咋一看有点复杂,我们可以来分析一下,主要思路是动态规划:

  1. 首先我们需要定义状态:用一个二维数组(套路)dp[i][j]用来表示str的前i个字符和pattern的前j个字符是否匹配。

  2. 接下来,我们需要初始化简单状态,因为想要求后面的状态,是依赖于前面的状态的,一般是初始化dp[i][j]的首行和首列。

  • dp[0][0]= true,表示两个空的字符串是匹配的。
  • dp数组的首列,除了dp[0][0]true,其他的都是false。因为pattern为空,但是s不为空的时候,肯定不匹配。
  • dp的首行,也就是str为空的时候,如果pattern的偶数位都是“*”,那么就可以匹配,因为可以选择匹配0次。

初始化前面之后,后面的从索引1开始匹配:

  • 2.1 如果dp[i - 1][j - 1]=true and str[i - 1] == pattern[j - 1]时,则dp[i][j]=true。(也就是前面匹配,接下来的字符一样匹配)
  • 2.2 如果dp[i - 1][j - 1]=truepattern[i-1]=='.',那么dp[i][j]=true。(其实也是.可以匹配任何字符)
  • 1.1 如果dp[i][j-2]==true,那么dp[i][j]=true(相当于str的前i和pattern的前j-2个字符匹配,此时的*前面的那个字符出现了0次)。
  • 1.2 如果dp[i-1][j]==truestr[i-1]==pattern[j-2],则dp[i][j] =true。(如果str的前i - 1个字符和pattern的前j个字符匹配,并且str的第i个字符和pattern的第j - 1个字符相等,相当于‘*’前面的字符出现了1次)
  • 1.3 如果dp[i-1][j]=truepattern[j-2]=='.'的时候,则dp[i][j]=true。(表示str的前i-1个和patten的前j个匹配,并且pattern的第j-1个是‘.’,第j个是‘*’,那么说明可以匹配任何字符任何次数,自然str可以多匹配一个字符。)
  1. pattern的第j个字符不为“*”(即是pattern[j-1]!='*')
  2. pattern的第j个字符为“*”(即是 pattern[j-1]=='*')

处理完数组之后,最后返回dp[n-1][m-1],也就是str的前n个和pattern的前m个字符是否匹配。

  public boolean match(String str, String pattern) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        int n = str.length() + 1;
        int m = pattern.length() + 1;
        boolean[][] dp = new boolean[n][m];
        dp[0][0] = true;
        for (int j = 2; j < m; j = j + 2) {
            if (dp[0][j - 2] && pattern.charAt(j - 1) == '*') {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (pattern.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]
                            || dp[i - 1][j] && (str.charAt(i - 1) == pattern.charAt(j - 2)
                            || pattern.charAt(j - 2) == '.');
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (str.charAt(i - 1) == pattern.charAt(j - 1)
                            || pattern.charAt(j - 1) == '.');
                }

            }
        }
        return dp[n - 1][m - 1];
    }

时间复杂度 O(mn) : 其中 m,n 分别为 strpattern 的长度,状态转移需遍历整个 dp 矩阵。
空间复杂度 O(mn): 状态矩阵 dp 使用 O(mn)的额外空间。

【刷题笔记】
Github仓库地址:https://github.com/Damaer/codeSolution
笔记地址:https://damaer.github.io/codeSolution/

【作者简介】
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:Java源码解析,JDBC,Mybatis,Spring,redis,分布式,剑指Offer,LeetCode等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。

2020年我写了什么?

开源刷题笔记

平日时间宝贵,只能使用晚上以及周末时间学习写作,关注我,我们一起成长吧~

上一篇:52.函数的参数


下一篇:爆肝,52条SQL语句,性能优化,干货必收藏 !