每天 每周 偶尔一道算法题: 正则表达式匹配
Puzzle
Puzzle from leetcode:
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Solution
其实一开始我是打算用c++自带的正则表达式库的,敲完#include <regex>
后觉得这样不太好,毕竟是在做算法题

那就暴力流来一波!首先考虑没有通配符的情况下, 比较完一位再比较下一位,很自然地想到递归:
1 2 3 4 5 6 7 8 9
| class Solution { public: bool isMatch(const string& s, const string& p) { if (p.empty()) { return s.empty(); } return (s[0] == p[0]) && isMatch(s.substr(1), p.substr(1)); } };
|
加上通配符**”.”**的情况也比较容易,只需要检查一下字符串在该位有字符即可:
1 2 3 4 5 6 7 8 9 10
| class Solution { public: bool isMatch(const string& s, const string& p) { if (p.empty()) { return s.empty(); } bool currentMatch = (s[0] == p[0]) || (p[0] == '.' && !s.empty()); return currentMatch && isMatch(s.substr(1), p.substr(1)); } };
|
然后是通配符**”*“**,这个有点麻烦需要去搜字符串后面几位,匹配0次的情况即return isMatch(s, p.substr(2))
,直接跳过当前字符后后面的”*”, 匹配1次的情况即return (currentMatch && isMatch(s.substr(1), p))
, 把待匹配字符串后移一位,然后继续递归:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public: bool isMatch(const string& s, const string& p) { if (p.empty()) { return s.empty(); } bool currentMatch = (s[0] == p[0]) || (p[0] == '.' && !s.empty()); if (p[1] == '*' && p.length() >= 2) { return isMatch(s, p.substr(2)) || (currentMatch && isMatch(s.substr(1), p)); } return currentMatch && isMatch(s.substr(1), p.substr(1)); } };
|
试了几个测试例,感觉还行哈~~

然后提交完结果出来了:

看来我还是too naive…

看了下提示,大意是用动态规划,先写状态转移方程:
定义dp[i][j] 在 s[0,i-1]和p[0,j-1]匹配时为正,反之为假
- 当没有通配符*****时:dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])
- 当有通配符*****时:
- 重复0次:dp[i][j] = dp[i][j-2]
- 重复1次:dp[i][j] = dp[i-1][j] && (s[i-1] == p[j-2])
贴一下代码(这里优化了一下,照着上面的写空间复杂度会到O(i*j), 下面的为O(N))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: bool isMatch(const string& s, const string& p) { int m = s.length(), n = p.length(); vector<bool> dp(n + 1, false); for (int i = 0; i <= m; i++) { bool pre = dp[0]; dp[0] = !i; for (int j = 1; j <= n; j++) { bool temp = dp[j]; if (p[j - 1] == '*') { dp[j] = dp[j - 2] || (i && dp[j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')); } else { dp[j] = i && pre && (s[i - 1] == p[j - 1] || p[j - 1] == '.'); } pre = temp; } } return dp[n]; } };
|
