实现支持.和*的正则表达式匹配.
思路: 动态规划
用f[i][j] 表示s中的前i 个字母能否与p 中的前j 个字母匹配, 按照p[j]是否为*分为两种情况
存在*时的转移方程可以这样考虑:
匹配 s 末尾的一个字符,将该字符扔掉,而该组合还可以继续进行匹配;(f[i−1][j])
不匹配字符,将该组合扔掉,不再进行匹配。(f[i][j−2])
最终的状态转移方程:
f[i][j]=⎩⎨⎧f[i−1][j−1],false,f[i][j−2] or f[i−1][j],f[i][j−2],p[j]=′∗′ and s[i]=p[j]p[j]=′∗′ and s[i]=p[j]p[j]=′∗′ and s[i]=p[j−1]p[j]=′∗′ and s[i]=p[j−1]
代码:
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
| class Solution { public: bool isMatch(string s, string p) { int m = s.size(); int n = p.size();
auto matches = [&](int i, int j) { if (i == 0) { return false; } if (p[j - 1] == '.') { return true; } return s[i - 1] == p[j - 1]; };
vector<vector<int>> f(m + 1, vector<int>(n + 1)); f[0][0] = true; for (int i = 0; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (p[j - 1] == '*') { f[i][j] |= f[i][j - 2]; if (matches(i, j - 1)) { f[i][j] |= f[i - 1][j]; } } else { if (matches(i, j)) { f[i][j] |= f[i - 1][j - 1]; } } } } return f[m][n]; } };
|