动态规划之正则表达

GitHub undefined undefined undefined

培养框架思维,真正爱上算法!关注公众号查看更新文章👆

相关推荐:

读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目:

10.正则表达式匹配(困难)


正则表达式是一个非常强力的工具,本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「正则表达式匹配」就要求我们实现一个简单的正则匹配算法,包括「.」通配符和「*」通配符。

这两个通配符是最常用的,其中点号「.」可以匹配任意一个字符,星号「*」可以让之前的那个字符重复任意次数(包括 0 次)。

比如说模式串 ".a*b" 就可以匹配文本 "zaaab",也可以匹配 "cb";模式串 "a..b" 可以匹配文本 "amnb";而模式串 ".*" 就比较牛逼了,它可以匹配任何文本。

题目会给我们输入两个字符串 sps 代表文本,p 代表模式串,请你判断模式串 p 是否可以匹配文本 s。我们可以假设模式串只包含小写字母和上述两种通配符且一定合法,不会出现 *a 或者 b** 这种不合法的模式串,

函数签名如下:

bool isMatch(string s, string p);

对于我们将要实现的这个正则表达式,难点在那里呢?

点号通配符其实很好实现,s 中的任何字符,只要遇到 . 通配符,无脑匹配就完事了。主要是这个星号通配符不好实现,一旦遇到 * 通配符,前面的那个字符可以选择重复一次,可以重复多次,也可以一次都不出现,这该怎么办?

对于这个问题,答案很简单,对于所有可能出现的情况,全部穷举一遍,只要有一种情况可以完成匹配,就认为 p 可以匹配 s。那么一旦涉及两个字符串的穷举,我们就应该条件反射地想到动态规划的技巧了。

一、思路分析

我们先脑补一下,sp 相互匹配的过程大致是,两个指针 i, j 分别在 sp 上移动,如果最后两个指针都能移动到字符串的末尾,那么久匹配成功,反之则匹配失败。

正则表达算法问题只需要把住一个基本点:看两个字符是否匹配,一切逻辑围绕匹配/不匹配两种情况展开即可​

如果不考虑 * 通配符,面对两个待匹配字符 s[i]p[j],我们唯一能做的就是看他俩是否匹配:

bool isMatch(string s, string p) {
    int i = 0, j = 0;
    while (i < s.size() && j < p.size()) {
        // 「.」通配符就是万金油
        if (s[i] == p[j] || p[j] == '.') {
            // 匹配,接着匹配 s[i+1..] 和 p[j+1..]
            i++; j++;
        } else {
            // 不匹配
            return false;
        }
    }
    return i == j;
}

那么考虑一下,如果加入 * 通配符,局面就会稍微复杂一些,不过只要分情况来分析,也不难理解。

p[j + 1]* 通配符时,我们分情况讨论下

1、如果 s[i] == p[j],那么有两种情况:

1.1 p[j] 有可能会匹配多个字符,比如 s = "aaa", p = "a*",那么 p[0] 会通过 * 匹配 3 个字符 "a"

1.2 p[i] 也有可能匹配 0 个字符,比如 s = "aa", p = "a*aa",由于后面的字符可以匹配 s,所以 p[0] 只能匹配 0 次。

2、如果 s[i] != p[j],只有一种情况:

p[j] 只能匹配 0 次,然后看下一个字符是否能和 s[i] 匹配。比如说 s = "aa", p = "b*aa",此时 p[0] 只能匹配 0 次。

综上,可以把之前的代码针对 * 通配符进行一下改造:

if (s[i] == p[j] || p[j] == '.') {
    // 匹配
    if (j < p.size() - 1 && p[j + 1] == '*') {
        // 有 * 通配符,可以匹配 0 次或多次
    } else {
        // 无 * 通配符,老老实实匹配 1 次
        i++; j++;
    }
} else {
    // 不匹配
    if (j < p.size() - 1 && p[j + 1] == '*') {
        // 有 * 通配符,只能匹配 0 次
    } else {
        // 无 * 通配符,匹配无法进行下去了
        return false;
    }
}

整体的思路已经很清晰了,但现在的问题是,遇到 * 通配符时,到底应该匹配 0 次还是匹配多次?多次是几次?

你看,这就是一个做「选择」的问题,要把所有可能的选择都穷举一遍才能得出结果。动态规划算法的核心就是「状态」和「选择」,「状态」无非就是 ij 两个指针的位置,「选择」就是 p[j] 选择匹配几个字符

二、动态规划解法

根据「状态」,我们可以定义一个 dp 函数:

bool dp(string& s, int i, string& p, int j);

_____________

本文只能在 labuladong 公众号查看,关注后可直接搜索本站内容:

Copyright © labuladong 2020 all right reserved,powered by Gitbook该文件修订时间: 2021-04-19 18:19:23

results matching ""

    No results matching ""