剑指Offer（五十二）-- 正则表达式匹配（动态规划）

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

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

示例1输入

"aaa","a*a"

返回值

true

思路以及解答

这道题，仔细一想，感觉情况很多，很凌乱，前面介绍的是递归的做法：剑指Offer（五十二）-- 正则表达式匹配（递归实现）

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

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次。

3.初始化前面之后，后面的从索引1开始匹配：

• 1.pattern的第j个字符为“*”(即是 pattern[j-1]=='*')
  • 1.1如果dp[i][j-2]==true，那么dp[i][j]=true(相当于str的前i和pattern的前j-2个字符匹配，此时的*前面的那个字符出现了0次)。
  • 1.2如果dp[i-1][j]==true且str[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]=true且pattern[j-2]=='.'的时候，则dp[i][j]=true。(表示str的前i-1个和patten的前j个匹配，并且pattern的第j-1个是‘.’，第j个是‘*’,那么说明可以匹配任何字符任何次数，自然str可以多匹配一个字符。)
• 2.pattern的第j个字符不为“*”(即是pattern[j-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]=true且pattern[i-1]=='.'，那么dp[i][j]=true。(其实也是.可以匹配任何字符)

处理完数组之后，最后返回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 分别为 str 和 pattern 的长度，状态转移需遍历整个 dp 矩阵。

空间复杂度 O(mn)：状态矩阵 dp 使用 O(mn)的额外空间。

【作者简介】：

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

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -