正则表达式匹配：进阶版

经典正则表达式问题

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
'’ 匹配零个或多个元素

通常该问题的求解采取动态规划，即dp[i][j]表示s的前i部分，与p串的前j部分是否能够匹配。

每次研究s[i]与p[j]的匹配情况完成 dp[][]数组的迭代填充，注意初始化dp[0][0] = true

进阶问题

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
'’ 匹配零个或多个前面的那一个元素

问题修改为前面那个元素，因此需要特别考虑*的情况。
容易知道匹配过程包含三种：

s[i-1]p[j-1] || p[j-1]‘.’ 此时dp[i][j]取决于前面部分的匹配结果，即：
dp[i-1][j-1]

p[j-1]==‘*’ 此时需要考察*的前部分，若为普通字母，那可以分为三小类：

其一，匹配0个，即dp[i][j-2]能够完成匹配，那么此时可以通过匹配0个，使得dp[i][j] = true
其二，匹配1个，即dp[i][j-1]能够匹配，其隐含意思是s[i-1]==p[j-2] 那么通过匹配一个，可以使得dp[i][j]=true
其三，匹配多个，其需要研究p[j-2]==s[i-1] 并且 dp[i-1][j]==true 即需要s串为最后两个为相同，并且和p串末尾匹配

特殊情况

若出现 “.*”的情况，那么这两个字符可以表示任意串，那么使得dp[i][j]=true的情况，可以为p的前面j-2部分与 s串的任意前缀部分匹配即可。

因此出现该情况时，只需要遍历 dp[k][j-2]即可（其中k<=i），一旦出现true，那么满足

代码实现

class Solution {
public:
    bool isMatch(string s, string p) {
   

      int len1 = s.size();
      int len2 = p.size();
      if(len1==0)
      {
          if(len2==0)
             return true;
      }
      if(len2==0)
      {
          return false;
      }
      vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false));//标记转移数组
      dp[0][0] = true;//能够匹配
      //当模式串前面部分为*时 可以完成dp[0][k]=true的填充

      int k = 2;
      while(k<len2+1 && p[k-1]=='*')
      {
          dp[0][k]=true;
          k+=2;
      }
      for(int i=1;i<len1+1;i++)
       for(int j=1;j<len2+1;j++)  //研究s串前i个 与 p串前j个是否能够匹配
       {
           if(s[i-1]==p[j-1] || p[j-1]=='.')  //那么取决于前面部分
           {
               dp[i][j] = dp[i-1][j-1];
           }
           if(p[j-1]=='*') //
           {
               dp[i][j]=dp[i][j-2] || dp[i][j-1] || (p[j-2]==s[i-1] && dp[i-1][j]); //那么可以 *匹配0个 或者* 匹配一个
               //单独讨论 匹配多个情况

               //还需要单独讨论 .*的情况

               if(p[j-2]=='.')  //那么可以任意替代
               {
                   //那么只需要p串的前j-2部分 与 s串的前i部分任意一个前缀部分 匹配即可，剩下的由.来替换
                   for(int k=0;k<=i;k++)
                     if(dp[k][j-2])
                        dp[i][j] = true;
               }
           }

       }

     return dp[len1][len2];

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

易错点

需要单独考虑，当s串为空，但是p串可以匹配的情况，此时p串只能匹配空串，那么要求，偶数位必须全部为* 如 ab.c

      int k = 2;   //填充dp[0][k]可能为true的情况
      while(k<len2+1 && p[k-1]=='*')
      {
          dp[0][k]=true;
          k+=2;
      }
1
2
3
4
5
6