正则表达式匹配问题

1 正则表达式匹配

问题描述

• 请实现一个函数用来匹配包含’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

问题分析

• 可以使用动态规划。将字符串的规模增长的方向，作为动态变化的方向。状态变量表示当前的正则表达式，能够与之匹配。当规模发生变化时，保证字符串-1和正则表达式-1能够匹配。其实在这里感觉规模增长的方向，确实是有两个。但是状态变量的设置比较精巧。

问题分类

• 字符串匹配问题
• 动态规划
• 递归

1.1 正则表达式匹配——动态规划

选择策略

• 动态规划

算法设计

• 设s的长度为n ，pp 的长度为 m ；将 s 的第 i 个字符记为 s_i，p 的第 j个字符记为 p_j ，将 s 的前 i 个字符组成的子字符串记为s[:i] , 同理将 p 的前 j 个字符组成的子字符串记为 p[:j]p[:j] 。

• 因此，本题可转化为求s[:n] 是否能和p[:m] 匹配。

• 总体思路是从 s[:1]和 p[:1]是否能匹配开始判断，每轮添加一个字符并判断是否能匹配，直至添加完整个字符串s 和p 。展开来看，假设 s[:i]与 p[:j]可以匹配，那么下一状态有两种：

  1. 添加一个字符 si+1s_{i+1}si+1​后是否能匹配？
  2. 添加字符 pj+1p_{j+1}pj+1​后是否能匹配？

• 本题的状态共有 m \times nm×n 种，应定义状态矩阵 dpdp ，dp[i][j]代表 s[:i]与 p[:j]是否可以匹配。做好状态定义，接下来就是根据 「普通字符」 , 「.」 , 「*」三种字符的功能定义，分析出动态规划的转移方程。

1. 状态定义： 设动态规划矩阵 dp ， dp[i][j] 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。
2. 转移方程： 需要注意，由于 dp[0][0] 代表的是空字符的状态， 因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1] 。
   • 当 p[j - 1] = ‘*’ 时， dp[i][j] 在当以下任一情况为 truetrue 时等于 truetrue ：
     1. dp[i][j - 2]： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配.
     2. dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配；
     3. dp[i - 1][j] 且 p[j - 2] = ‘.’: 即让字符 ‘.’ 多出现 1 次时，能否匹配；

• 当 p[j - 1] != ‘*’ 时， dp[i][j] 在当以下任一情况为 truetrue 时等于 truetrue ：
  1. dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配；
  2. dp[i - 1][j - 1] 且 p[j - 1] = ‘.’： 即将字符 . 看作字符 s[i - 1] 时，能否匹配；
• 初始化： 需要先初始化 dp 矩阵首行，以避免状态转移时索引越界。
• 返回值 dp 矩阵右下角字符，代表字符串 s 和 p 能否匹配。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ppcWmD6q-1678256498154)(image/2021-03-18-20-39-26.png)]

算法分析

• 时间复杂度O(M*N)
• 空间复杂度O(M*N)

算法实现

class Solution {
public:bool isMatch(string s, string p) {int m = s.size() + 1, n = p.size() + 1;vector> dp(m, vector(n, false));dp[0][0] = true;for(int j = 2; j < n; j += 2)dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = p[j - 1] == '*' ?dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'):dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);}}return dp[m - 1][n - 1];}
};

1.2 正则表达式匹配——递归

选择策略

• 递归

算法设计

• 递归的参数：字符串string、模式pattern、int i、int j分别表示当前字符串匹配到的位置，和模式行进到的位置。
• 递归的返回值：返回值是当前分支是否成功。如果最后一个检测成果了，则返回true。如果最后没有检测成功，则返回false；
• 递归的执行：
  • 如果下一个是*号。进行多分支递归讨论。
    1. 匹配0次，i=i,j=j+2.进行下一轮递归。
    2. 匹配1次，判断这一次是否成功，如果成功i=i+1,j=j
  • 如果下一个不是*号。进行单分支递归。
    1. 匹配正常字符或者.。匹配成功。i=i+1,j=j+1
    2. 匹配不成功。return false；
• 递归的终止条件
  • i和j匹配都完成。return true；
  • 其他情况return false
• 递归前和递归后的处理

算法分析

• 时间复杂度O(M+N)
• 空间复杂度O(M)

算法实现

    bool isMatch(string s, string p) {return isMatchR(s,p,0,0);}// 递归和循环混搭，果然很恶心。直接使用递归好了。// 递归的条件判断。正则表达式。// 算法设计的关键是，选择一个好的算法技术（递归或循环，两个是冗余的。）// 然后设计好的算法路程。关键在于分类讨论的方式。如何合并类别。bool isMatchR(string &s,string &p,int i,int j){//递归终止的条件if(i>=s.size() && j>=p.size()){return true;}// cout<// 匹配零次 || 匹配一次return isMatchR(s,p,i,j+2) || ((ireturn isMatchR(s,p,i+1,j+1);}if(ireturn isMatchR(s,p,i+1,j+1);}// 不匹配return false;}