一位程序员,比较帅的那种

0%

Algorithm Puzzles: Regular Expression Matching

每天 每周 偶尔一道算法题: 正则表达式匹配

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 *.

Solving

其实一开始我是打算用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];
}
};