剑指offer - 正则表达式匹配

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c

题意

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

题解

假设dp[i][j]=true表示 s[0..i-1] 匹配 p[0..j-1]
则有两种情况，

  1. 如果p[j-1]!=’*’
    • 如果s[i-1]与p[j-1]匹配并且dp[i-1][j-1]为true，那么dp[i][j]为true
  2. 如果p[j-1]==’*’，假设p[j-2]=X
    • X* 匹配0次的情况，如果dp[i][j-2]为true，dp[i][j]为true
    • 如果匹配超过0次，如果dp[i-1][j]为true，也就是最后一位前面的位匹配，并且最后一位匹配，那么dp[i][j]为true。
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
class Solution {
public:
    bool match(char* str, char* pattern)
    {
        int m=strlen(str),n=strlen(pattern);
        vector< vector<bool> > dp(m+1,vector<bool>(n+1));
        //空和空匹配
        dp[0][0] = true;
        //匹配空模式串
        for(int i=1;i<=m;i++){
            dp[i][0]=false;
        }
        //空串匹配模式串
        for(int j=1;j<=n;j++){
            dp[0][j]=j>1&&pattern[j-1]=='*'&&dp[0][j-2];
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(pattern[j-1]!='*'){
                    dp[i][j]=dp[i-1][j-1]&&(pattern[j-1]==str[i-1]||pattern[j-1]=='.');
                }else{
                    dp[i][j]=dp[i][j-2]||(dp[i-1][j]&&(pattern[j-2]==str[i-1]||pattern[j-2]=='.'));
                }
            }
        }
        return dp[m][n];
    }
};