【面试算法——动态规划 21】正则表达式匹配(hard)&& 交错字符串

简介: 【面试算法——动态规划 21】正则表达式匹配(hard)&& 交错字符串

10. 正则表达式匹配

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

‘.’ 匹配任意单个字符

‘*’ 匹配零个或多个前面的那一个元素

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

示例 1:

输入:s = “aa”, p = “a”

输出:false

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

示例 2:

输入:s = “aa”, p = “a*”

输出:true

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

示例 3:

输入:s = “ab”, p = “."

输出:true

解释:".” 表示可匹配零个或多个(‘*’)任意字符(‘.’)。

1.状态表示*

dp[i][j] 表⽰:字符串 p 的 [0, j] 区间和字符串 s 的 [0, i] 区间是否可以匹配

2.状态转移方程

⽼规矩,根据最后⼀个位置的元素,结合题⽬要求,分情况讨论:

1. i. 当 s[i] == p[j] 或 p[j] == '. ’ 的时候,此时两个字符串匹配上了当前的⼀个字符,只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果, dp[i][j] = dp[i][j - 1] ;

ii. 当 p[j] == ‘*’ 的时候,此时匹配策略有两种选择:

• ⼀种选择是: * 匹配空字符串,此时相当于它匹配了⼀个寂寞,直接继承状态 dp[i] [j - 1] ,此时 dp[i][j] = dp[i][j -1] ;

• 另⼀种选择是: * 向前匹配 1 ~ n 个字符,直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中,选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ;

1. iii. 当 p[j] 不是特殊字符,且不与 s[i] 相等时,⽆法匹配。 三种情况加起来,就是所有可能的匹配结果。

综上所述,状态转移⽅程为:

▪ 当 s[i] == p[j] 或 p[j] == ‘?’ 时: dp[i][j] = dp[i][j - 1] ;

▪ 当 p[j] == ‘*’ 时,有多种情况需要讨论: dp[i][j] = dp[k][j - 1] (0 <=k <= i)

3. 初始化

由于 dp 数组的值设置为是否匹配,为了不与答案值混淆,我们需要将整个数组初始化为false 。

由于需要⽤到前⼀⾏和前⼀列的状态,我们初始化第⼀⾏、第⼀列即可。

dp[0][0] 表⽰两个空串能否匹配,答案是显然的,初始化为 true 。

第⼀⾏表⽰ s 是⼀个空串, p 串和空串只有⼀种匹配可能,即 p 串全部字符表⽰为"任⼀字符+*",此时也相当于空串匹配上空串。所以,我们可以遍历 p 串,把所有前导为"任⼀字符+"的 p ⼦串和空串的 dp 值设为 true 。

第⼀列表⽰ p 是⼀个空串,不可能匹配上 s 串,跟随数组初始化即可

4. 填表顺序

根据「状态转移⽅程」得:从上往下填写每⼀⾏,每⼀⾏从左往右

5. 返回值

返回 dp[m][n]

代码:

  bool isMatch(string s, string p) {
        int n=s.size();
        int m=p.size();
        //表示的是 s串中0~i 位置的子串,能否于 p串 0~j 上完全匹配
        vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
        //初始化
        dp[0][0]=true;
        for(int i=2;i<=m;i+=2)//初始化有坑
        {
            if(p[i-1]=='*') dp[0][i]=1;
            else break;
        }
      //填表
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s[i-1]==p[j-1]||p[j-1]=='.')
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                if(p[j-1]=='*')
                {
                    if(p[j-2]=='.')
                    {
                        dp[i][j]=dp[i][j-2]||dp[i-1][j];
                    }
                    else
                    {
                        if(p[j-2]==s[i-1])//相等的时候,
                        dp[i][j]=dp[i][j-2]||dp[i-1][j];
                        //当不相等的时候,也需要考虑匹配空串的情况
                        else dp[i][j]=dp[i][j-2];
                    }
                }
            }
        }
        return dp[n][m];
    }


df313d0c7a9c4eddbcac564d8946fc16.png


相关文章
|
1月前
|
算法
【优选算法】—— 字符串匹配算法
【优选算法】—— 字符串匹配算法
|
1月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
21 0
|
2月前
|
人工智能 算法 测试技术
【动态规划】【字符串】【C++算法】940. 不同的子序列 II
【动态规划】【字符串】【C++算法】940. 不同的子序列 II
|
10天前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
[Java·算法·简单] LeetCode 28. 找出字符串中第一个匹配项的下标 详细解读
21 0
|
1月前
|
算法 测试技术 索引
力扣面试经典题之数组/字符串(二)
力扣面试经典题之数组/字符串(二)
13 0
|
2月前
|
算法 测试技术 C++
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
【字符串】【 LCP】【C++算法】2573找出对应 LCP 矩阵的字符串
|
2月前
|
存储 算法
【编码狂想】LeetCode 字符串和数组篇:挑战算法精髓,深化程序设计基础
【编码狂想】LeetCode 字符串和数组篇:挑战算法精髓,深化程序设计基础
37 0
|
1月前
|
编译器 Python
Python正则表达式的7个使用典范(推荐)
Python正则表达式的7个使用典范(推荐)
22 0
|
1月前
|
Python
Python实现正则表达式匹配。
【2月更文挑战第11天】【2月更文挑战第30篇】Python实现正则表达式匹配。