点击蓝色“五分钟学算法”关注我哟

加个“星标”,一起学算法

深度解析「正则表达式匹配」:从暴力解法到动态规划

今天分享的题目来源于 LeetCode 上第 10 号问题:正则表达式匹配。题目难度为 Hard,目前通过率为 23.9% 。

温馨提示:本题目有点难,干货有点干,建议先收藏后再仔细阅读。

题目描述

给你一个字符串 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

题目解析

这道题其实是要实现 Regular Expression 里面的两个符号,一个是 ‘.’,另一个是 ‘*’, 前者表示可以 match 任意一个字符,后者表示其前面的字符可以重复零次或者多次。

题目的难点其实是在于 * 上面,如果没有这个 *,题目会变得非常简单,这里说一下题目的两个隐含条件:

  • 一个就是 * 不会出现在字符串的开头

  • 另外一个是 * 前面不能是 *,比如 “a * * b” 就不行

当然你也可以把这两个隐含条件当作一个来看,不管如何,我们的代码实现必须建立在这个基础之上,否则,case 考虑多了,题目将无从下手。

解法一:递归暴力求解

递归方式的暴力深度优先搜索求解方法往往是搜索问题的万金油,这里你只需要简单的考虑两件事情,一是这个问题是否可以划分为子问题,二是每个子问题有几种状态,就是在当前考虑的问题下,一共有多少种可能性

知道了这两点后,对于每个子问题的每一个状态递归求解就行。

上面说的可能有点抽象,结合这个题目来做例子,这里的问题是,输入一个字符串 s,以及其匹配字符串 p,要求解这两个字符串是否匹配。

我们首先考虑这个字符串比较的问题能不能划分为一个个的子问题,你发现字符串是可以划分成为一个个字符的,这样字符串比较的问题就会变成字符的比较问题,这样一来,我们就可以把问题看成,决定 s[i,…n] 是否能够匹配 p[j,…m] 的条件是子问题 s[i+1,…n] 能不能够匹配 p[j+1,…m],另外还要看 s[i] 和 p[j] 是否匹配,但是这里的当前要解决的问题是 s[i] 和 p[j] 是否匹配,只有这一点成立,我们才有继续递归去看 s[i+1,…n] 是匹配 p[j+1,…m],注意这里我说 s[i] p[j], 并不表示说当前就只用考虑这两个字符之间匹不匹配,它只是用来表示当前问题,这个当前问题也许只需要比较一个字符,也许要比较多个,这就引申出了前面提到的第二点,我们还需要考虑当前问题中的状态。

对于字符串 s 来说,没有特殊字符,当前问题中字符只会是字母,但是对于 p 来说,我们需要考虑两个特殊符号,还有字母,这里列举所有的可能,如果说当前的子问题是 s[i,…n] 和 p[j…m]:

  • s[i] == p[j],子问题成立与否取决于子问题 s[i+1,…n] 和 p[j+1,…m]

  • p[j] == ‘.’,子问题成立与否取决于子问题 s[i+1,…n] 和 p[j+1,…m]

  • p[j+1] == ‘*’,s[i] != p[j],子问题成立与否取决于子问题 s[i,…n] 和 p[j+2,…m]

  • p[j+1] == ‘*’,s[i] == p[j],子问题成立与否取决于子问题 s[i+1,…n] 和 p[j,…m]

这里我解释下第三种情况,之前在题目描述里说过,p 的起始字符不可能是 *,也就是说 * 的前面必须有字母,根据定义,这里我们可以把 * 的前面的元素个数算作是零个,这样我们就只用看,s[i,…n] 和 p[j+2,…n] 是否匹配,如果算作一个或者多个,那么我们就可以看 s[i+1,…n] 和 p[j,…m] 是否成立,当然这个的前提是 p[j] == s[i] 或者 p[j] == ‘.’, 我们可以结合代码来看看

class Solution {
    public boolean isMatch(String s, String p) {
    if (s.equals(p)) {
        return true;
    }

    boolean isFirstMatch = false;
    if (!s.isEmpty() && !p.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
        isFirstMatch = true;
    }

    if (p.length() >= 2 && p.charAt(1) == '*') {
        // 看 s[i,...n] 和 p[j+2,...m] 或者是 s[i+1,...n] 和 p[j,...m]
        return isMatch(s, p.substring(2))
                 || (isFirstMatch && isMatch(s.substring(1), p));
    }

    // 看 s[i+1,...n] 和 p[j+1,...m]
    return isFirstMatch && isMatch(s.substring(1), p.substring(1));
   }
}

上面的实现之所以被称为暴力求解是因为子问题的答案没有被记录,也就是说如果当前要用到之前的子问题的答案,我们还得去计算之前计算过的子问题。

解法二:记忆化搜索

上面的暴力解法是因为没有记录答案,记忆化搜索是在 “傻搜” 的基础之上添加 “记事本”。这里我把递归的方向给改变了,当然这不是必要的,主要想说明,对于递归来说,从后往前考虑和从前往后考虑都是可行的。

我们假设当前问题是考虑 s 的第 i 个字母,p 的第 j 个字母,所以这时的子问题是 s[0…i] 和 p[0…j] 是否匹配

  • p[j] 是字母,并且 s[i] == p[j],当前子问题成立与否取决于子问题 s[0…i-1] 和 p[0…j-1] 是否成立

  • p[j] 是 ‘.’,当前子问题成立与否取决于子问题 s[0…i-1] 和 p[0…j-1] 是否成立

  • p[j] 是字母,并且 s[i] != p[j],当前子问题不成立

  • p[j] 是 ‘*’,s[i] == p[j – 1],或者 p[j – 1] == ‘.’, 当前子问题成立与否取决于子问题 s[0…i-1] 和 p[0…j] 是否成立

  • p[j] 是 ‘*’,s[i] != p[j – 1],当前子问题正确与否取决于子问题 s[0…i] 是否匹配 p[0,…j-2]

不管是从前往后,还是从后往前,你可以看到,考虑的点都是一样的,只是这里我们多加了一个 “记事本”

public boolean isMatch(String s, String p) {
    if (s.equals(p)) {
        return true;
    }

    boolean[] memo = new boolean[s.length() + 1];

    return helper(s.toCharArray(), p.toCharArray(), 
                  s.length() - 1, p.length() - 1, memo);
}

private boolean helper(char[] s, char[] p, int i, int j, boolean[] memo) {
    if (memo[i + 1]) {
        return true;
    }

    if (i == -1 && j == -1) {
        memo[i + 1] = true;
        return true;
    }

    boolean isFirstMatching = false;

    if (i >= 0 && j >= 0 && (s[i] == p[j] || p[j] == '.' 
          || (p[j] == '*' && (p[j - 1] == s[i] || p[j - 1] == '.')))) {
        isFirstMatching = true;
    }

    if (j >= 1 && p[j] == '*') {
        // 看 s[0,...i] 和 p[0,...j-2] 
        boolean zero = helper(s, p, i, j - 2, memo);
        // 看 s[0,...i-1] 和 p[0,...j]
        boolean match = isFirstMatching && helper(s, p, i - 1, j, memo);

        if (zero || match) {
            memo[i + 1] = true;
        }

        return memo[i + 1];
    }

    // 看 s[0,...i-1] 和 p[0,...j-1]
    if (isFirstMatching && helper(s, p, i - 1, j - 1, memo)) {
        memo[i + 1] = true;
    }

    return memo[i + 1];
}

解法三:动态规划

有了上面两种方法和解释作为铺垫,我想迭代式的动态规划应该不难理解。这里我们不再用递归,而是使用 for 循环的形式,先上代码:

public boolean isMatch(String s, String p) {
    if (s.equals(p)) {
        return true;
    }

    char[] sArr = s.toCharArray();
    char[] pArr = p.toCharArray();

    // dp[i][j] => is s[0, i - 1] match p[0, j - 1] ?
    boolean[][] dp = new boolean[sArr.length + 1][pArr.length + 1];

    dp[0][0] = true;

    for (int i = 1; i <= pArr.length; ++i) {
        dp[0][i] = pArr[i - 1] == '*' ? dp[0][i - 2] : false;
    }

    for (int i = 1; i <= sArr.length; ++i) {
        for (int j = 1; j <= pArr.length; ++j) {
            if (sArr[i - 1] == pArr[j - 1] || pArr[j - 1] == '.') {
                // 看 s[0,...i-1] 和 p[0,...j-1]
                dp[i][j] = dp[i - 1][j - 1];
            }

            if (pArr[j - 1] == '*') {
                // 看 s[0,...i] 和 p[0,...j-2]
                dp[i][j] |= dp[i][j - 2];

                if (pArr[j - 2] == sArr[i - 1] || pArr[j - 2] == '.') {
                    // 看 s[0,...i-1] 和 p[0,...j]
                    dp[i][j] |= dp[i - 1][j];
                }
            }
        }
    }

    return dp[sArr.length][pArr.length];
}

这里我说一下前面的 DP 数组的初始化,因为需要考虑空串的情况,所以我们 DP 数组大小多开了 1 格。dp[0][0] = true 因为两个空串是匹配的,紧接着下面一行的 for 循环是为了确保空串和 p 的一部分是匹配,比如 s = “”,p = “a*b”,那么这里 dp[0][2] = true,也就是 s[0,0]和p[0,2] 是匹配的,注意和之前不一样的是这里的 0 代表空串。

字符串匹配类动态规划的总结和思考

一般来说,对于字符串匹配的问题中,输入参数都会有两个字串,如果确定了这道题的问题是可以分解成一系列子问题,那么就可以考虑使用动态规划求解,可以根据区间来定义状态,一般来说只需要考虑头区间或者是尾区间,这道题中的动态规划解法,我们就是考虑了头区间,s[0,…i]和p[0,…j] 是否匹配记录在 dp[i+1][j+1] 中,如果你选择尾区间的话,那么遍历的方式需要从后往前,就和之前讲解的记忆化搜索一样。所以一般的字符串匹配的动态规划的 DP 数组都是二维的,当然也有特例。个人觉得确定了考虑的区间和遍历方向,至少来说在动态规划状态方程的推导上会清晰不少。

接下来就是重点的部分,递推方程的推导,这里没有特别多的技巧,还是那句话,唯手熟尔,无他,要说重点的话,还是在确定当前子问题和前面子问题的联系上吧,或者你可以这样想 “当前考虑的子问题在什么情况下会变成前面求解过的子问题”。

还是拿这道题举例,上面的 DP 解法我们从前往后遍历,在考虑子问题 s[0,…i]和p[0,…j] 是否匹配,如果拿掉 s[i] 和 p[j],这个问题就会变成前面求解过的子问题 s[0,…i-1]和p[0,…j-1],如果只拿掉 s[i],这个问题就会变成前面求解过的子问题 s[0,…i-1]和p[0,…j],如果只拿掉 p[j-1,j],这个问题就会变成前面求解过的子问题 s[0,…i]和p[0,…j-2],至于为什么有些可以拿掉,有些不能,那这个只能根据题意来分析了,相信通过前面的分析应该不难理解。

结合上面的分析,这里列了一些字符串匹配类动态规划的一些注意事项:

  • 注意考虑是否需要考虑空串的情况,如果是的话,一般 DP 数组需要多开一格

  • 在考虑递推方程前,确定子问题的区间和遍历方向

  • 在思考递推方程的时候,重点思考当前子问题怎么变成之前求解过的子问题

以上就是全部,希望对于你理解这道题,或者说是理解字符串匹配类动态规划有所帮助。



本文相关阅读推荐:


毕业十年后,我忍不住出了一份程序员的高考试卷

一道腾讯面试题:厉害了我的杯

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

这或许是东半球分析十大排序算法最好的一篇文章

面试官,我会写二分查找法!对,没有 bug 的那种!

看《长安十二时辰》可以了解哪些算法知识

GitHub 标星 3w+,很全面的算法和数据结构知识

深度解析「正则表达式匹配」:从暴力解法到动态规划