动态规划（DP）解正则匹配

vlambda
2020-03-11

动态规划（DP）解正则匹配

实在抱歉，第一次拖更。。。因为想更详细的写清楚解题思路，所以又是画图又是修改讲题思路，之后注意。

嗨，各位！我们又准时见面了，如约而至的动态规划常见题目来了，今天来一道相对来说不是很好理解，却又常常出现在我们身边的一道场景题目，实现一个阉割版的正则表达式匹配。

话不多说，我们先看题目：

01 . 题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

说明:s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:输入: s = "aa" p = "a"输出: false

解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:输入: s = "aa" p = "a*"输出: true

解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:输入: s = "ab" p = ".*"输出: true

解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:输入: s = "aab" p = "c*a*b"输出: true

解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:输入: s = "mississippi" p = "mis*is*p*."输出: false

02 . 思路分析

正则表达式本身就是我们平时写代码经常用到的，这道题是一个阉割版本的正则表达式，只有“.” 和 “*” 两个元字符，我们开始分析题目：

我们在下文中把需要匹配的原字符串和对应的表达式分别称为原字符串s和正则串p，正则串一共会出现如下几种情况：

'ab'    直接就是具体的字符'a*'    某个字符和'*'来表达0-n个某个字符'.' 表示对应任意的一个字符'.*'    表示0-n个任意一个字符

再继续归类的话，我们可以将 'a*' 和 '.*' 归为一类，也就是说代表的是某个字符的0~n次重复。

动态规划思路的核心就是把问题分解成子问题并找到对应的状态转移方程。如果我们尝试建立一个二维数组dp[i][j]，来表示前j个正则字符是否能匹配前i个字符（特别说明一下，因为有空字符串和空匹配串的可能，所以dp[i][j] 所表示的最后一个字符串字符和匹配字符为s[i - 1] 和 p[j - 1]），那么我们求出dp[s.length][p.length](s代表字符串，p代表匹配串)，就是我们这道题的答案。

想要求出dp[s.length][p.length]，我们继续研究是否能通过一个公式，来找出dp[i][j] (i, j 是泛指某两个值)与 dp[i - 1][j]， dp[i][j - 1] 等前置状态的关系，从而推导出状态转移方程既dp[i][j] = ？我们先看一些基础的初始化情况：

先看dp[0][0]，代表空字符串和空正则串，那么他们是匹配的，dp[0][0] = true

再看dp[0][1] ~ dp[0][j.length]，首先dp[0][1]，没有办法用一个字符长度的正则串去匹配一个空字符串，所以dp[0][1] = false。从dp[0][2] 开始，如果匹配串的第二个字符是'*'，则无论第一个字符是什么都是可以匹配空字符串的。以此类推dp[0][3/5/7]奇数个都是不行的，dp[0][2/4/6]等要看具体的匹配字符串的构成是否是某个字符/'.' 与 '*' 的组合，需要具体的讨论，可以有一层循环来解决，且dp[0][j] = dp[0][j - 2] && p[j-1] == '*'

再来看dp[1][0]，这个不用讨论，空匹配串肯定不能匹配非空字符串，既dp[1][0] = false。

之后我们开始讨论通用的dp[i][j]的各类情况：

如果p[j - 1] 是一个正常字符或者是'.'，则直接判断对应的s[i - 1] 是否相等即可，代码的话则可以通过 s[i - 1] == p[j - 1] || p[j - 1] == '.' 来判断。

如果p[j - 1] 是 '*' 的话，我们需要分类来进行讨论：

1. 如果dp[i][j - 2] 是 true 的话那么 dp[i][j]也是 true，我们通过图示来看一下：

也就是说，如果之前的字符串和匹配串是匹配的，那么字符串不变，匹配串增加一个'X*' （X代表任意字符或 '.'），也同样可以匹配，图示的例子表示的就是：

'AB' 可以被 'AB' 匹配，也同时可以被 'ABD*' 匹配。

2. 如果dp[i - 1][j] 是 true 并且s[i - 1] == p [j - 2]的话那么 dp[i][j]也是 true，我们通过图示来看一下：

如上图所示，如果之前的字符串能被一个以'*'结尾的匹配串匹配，那么如果字符串增加一个与'*'前的匹配字符相同的字符（两种情况，第一种 'D' == 'D'，第二种 '任意字符' == '.' ），也就是说为什么不是拿s[i - 1] 与 s[i - 2]去匹配的原因，他存在匹配串的字符是 '.' 的可能，下面这张图说明了特殊情况：

动态规划（DP）解正则匹配

这种特殊情况，可以通过前面说到的用当前字符串的最后一个字符与匹配串的对应字符去匹配，而不是直接比对之前的一个字符串字符。

综上所述，我们求出了一个状态转移方程：

dp[i][j] = dp[i][j - 2]        || dp[i - 1][j] && check(i, j-1)

结合之前的各类初始化情况，我们尝试写出解题代码：

/** * @param {string} s * @param {string} p * @return {boolean} */var isMatch = function(s, p) { let sl = s.length let pl = p.length let dp = []
 // 判断相等 a == a || a == . function check(si, pi){ // si pi 代表第几个数字 不涉及0 开头的问题 return s[si - 1] == p[pi - 1] || p[pi - 1] == '.' }
 // dp初始化 for(let i = 0; i <= sl; i++){ dp[i] = [] } dp[0][0] = true for(let j = 2; j <= pl; j++){ dp[0][j] = p[j - 1] == '*' && dp[0][j - 2] }  // dp转移方程 空字符串或空正则的情况已经在上边处理了可能为true的情况 // 利用js特性 undefined 为 false 无需显示声明 for(let i = 1; i <= sl; i++){ for(let j = 1; j <= pl; j++){ // 状态转移方程 分类讨论 if(p[j - 1] == '*'){ dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && check(i, j-1) }else{ // 当前正则字符不是 *  dp[i][j] = dp[i - 1][j - 1] && check(i, j) } } } console.log(dp) return !!dp[sl][pl]};

这道题到这里就结束了，大家可以自己练练手，最后祝大家周末愉快，因为时间原因，只能推迟到明天做一个《动态规划解题的常见题集合》，之后还是多存点货吧，不然突然有点啥事儿，就耽搁了更新。

如果你觉得文章的内容能给你带来收获，欢迎关注 + 点赞在看 + 转发，更期待你能推荐给身边的小伙伴，让我们一起来梳理前端知识！一起加油！

「往期回顾」

文章涉及到源码已经在github中开源

让我知道你在看

vlambda博客
学习文章列表