【面试算法——动态规划 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


相关文章
|
3月前
|
存储 算法
深入了解动态规划算法
深入了解动态规划算法
85 1
|
3月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
5月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
2月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
67 2
|
3月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
122 2
动态规划算法学习三:0-1背包问题
|
3月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
111 1
两个字符串匹配出最长公共子序列算法
|
3月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
85 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
3月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
199 0
动态规划算法学习二:最长公共子序列
|
3月前
|
存储 人工智能 算法
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
|
3月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
202 0