《剑指offer刷题笔记》18、正则表达式匹配【c++详细题解】

喜欢ヅ旅行 2021-07-24 23:58 183阅读 0赞

### 题目 ###

请实现一个函数用来匹配包括`'.'`和`'*'`的正则表达式。

模式中的字符`'.'`表示任意一个字符，而`'*'`表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串`"aaa"`与模式`"a.a"`和`"ab*ac*a"`匹配，但是与`"aa.a"`和`"ab*a"`均不匹配。

**样例**

输入：
    
    s="aa"
    p="a*"
    
    输出:true

### **思路** ###

**(动态规划)** O ( n m ) O(nm) O(nm)

状态表示：`f[i][j]`表示p从j开始到结尾，是否能匹配s从i开始到结尾  
状态转移：

1.  如果`p[j+1]`不是通配符`'*'`，则`f[i][j]`是真，当且仅当`s[i]`可以和`p[j]`匹配，且`f[i+1][j+1]`是真；
2.  如果`p[j+1]`是通配符`'*'`，则下面的情况只要有一种满足，`f[i][j]`就是真；
    
     *  `f[i][j+2]`是真；这这里表示0个p\[j\]
     *  `s[i]`可以和`p[j]`匹配，且`f[i+1][j]`是真；

第1种情况下的状态转移很好理解，那第2种情况下的状态转移怎么理解呢？

最直观的转移方式是这样的：枚举通配符`'*'`可以匹配多少个`p[j]`，只要有一种情况可以匹配，则`f[i][j]`就是真；  
这样做的话，我们发现，`f[i][j]`除了枚举0个`p[j]`之外，其余的枚举操作都包含在`f[i+1][j]`中了，所以我们只需判断  
`f[i+1][j]`是否为真，以及`s[i]`是否可以和`p[j]`匹配即可。

时间复杂度分析： n n n 表示 s s s的长度， m m m 表示p的长度，总共  n m nm nm 个状态，状态转移复杂度  O ( 1 ) O(1) O(1)，所以总时间复杂度是  O ( n m ) O(nm) O(nm).

### **代码** ###

class Solution { 
    public:
        vector<vector<int>>f;
        int n, m;
        bool isMatch(string s, string p) { 
            n = s.size();
            m = p.size();
            f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
            return dp(0, 0, s, p);
        }
    
        bool dp(int x, int y, string &s, string &p)
        { 
            if (f[x][y] != -1) return f[x][y];
            if (y == m)
                return f[x][y] = x == n;
            bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
            bool ans;
            if (y + 1 < m && p[y + 1] == '*')
            { 
                ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
            }
            else
                ans = first_match && dp(x + 1, y + 1, s, p);
            return f[x][y] = ans;
        }
    };