8000 added 127. Regular Expression Matching · albertleers/LeetCode@fc23ebe · GitHub
[go: up one dir, main page]
Skip to content

Commit fc23ebe

Browse files
pezypezy
committed
added 127. Regular Expression Matching
1 parent 41eacd7 commit fc23ebe

File tree

3 files changed

+78
-0
lines changed

3 files changed

+78
-0
lines changed

‎127. Regular Expression Matching/README.md

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
讨厌这种不清不楚的题目。
2+
3+
`.` 代表任意单字符，`*` 可以代表将前面的字符去掉，也可以代表是对前面字符的重复（数目无限）。
4+
5+
下面分析题目中给出的例子：
6+
7+
aa a // 不匹配，很明显
8+
aa aa // 匹配，也很明显
9+
aaa aa // 不匹配
10+
aa a* // 匹配，* 可以重复为a
11+
aa .* // 匹配，. 可以是 a, * 可以重复 a。
12+
ab .* // 匹配，等等，不对啊，什么玩意。先放一放。
13+
aab c*a*b // 匹配，第一个 * 可以是 0，剩下 a*b，* 可以是 a 的重复，则 aab 匹配。
14+
15+
貌似唯一的疑问出在 `ab .*` 的匹配上。这个我也困惑了好久好久。无奈之下查看了[讨论](https://leetcode.com/discuss/4514/ismatch-ab-%E2%86%92-true-why-ab-c-expected-false)
16+
17+
摘录让我醍醐灌顶的解释：
18+
19+
> `.*` means zero or any occurrence of `.`, which can be (no dot at all), `.`, `..`, `...`, etc. `aab` matches `...`, which is one of the possible meanings of `.*`, `ab` matches `..` which is another possible meaning of `.*`. So `isMatch("ab",".*") = isMatch("aab", ".*") = True`.
20+
21+
> So in short, `.*` can match any string.
22+
23+
> One step further, `.*c` matches any string ending with `c`, which does not include `ab`. So `isMatch("ab", ".*c") = False`
24+
25+
> -----
26+
> by @MoonKnight
27+
28+
是否看明白了呢？`.*`中 `*` 重复的并不是某一个特定的字符，而是 `.` 本身。所以 `.*` 可以是 `..`。
29+
这样一来，第一个`.`匹配`a`，第二个`.`匹配`b`。这不就与`ab`匹配上了吗？
30+
31+
再往远了想一想，`.*` 可以匹配任意字符串啊。（本质在于咱们脑子里规定了一个与出题人不一致的顺序，我们认为要先确定`.`，然后再去看 `*`。）
32+
33+
说这题不清不楚，没说错吧。如果你一开始就能会意，恭喜你了。
34+
35+
-----
36+
37+
我的思路是，要判断字符串，肯定要从字符开始。这就简化了问题，比较两个字符是否匹配很容易。
38+
39+
```cpp
40+
// char s,p;
41+
if (s == p || (p == '.' && s != '\0')) // same character.
42+
```
43+
44+
首先，迭代 `p`，如果 `*p == '\0'`，那么可以直接返回 `return *s == '\0';`
45+
46+
其次，判断后面有没有跟`*`，即 `if (p[1] != '*')` 那么就正常比较当前字符。若跟了 `*`，
47+
则与判断 `isMatch(s, p+2)` 无异。（因为 `*` 可以代表0）
48+
49+
最后，一旦出现不同字符，直接返回 `false`。
50+
51+
代码很简单，5行搞定。

‎127. Regular Expression Matching/TEST.cc

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
#define CATCH_CONFIG_MAIN
2+
#include "../Catch/single_include/catch.hpp"
3+
#include "solution.h"
4+
5+
TEST_CASE("Regular Expression Matching", "isMatch")
6+
{
7+
Solution s;
8+
9+
REQUIRE_FALSE(s.isMatch("aa", "a"));
10+
REQUIRE(s.isMatch("aa", "aa"));
11+
REQUIRE_FALSE(s.isMatch("aaa", "aa"));
12+
REQUIRE(s.isMatch("aa", "a*"));
13+
REQUIRE(s.isMatch("aa", ".*"));
14+
REQUIRE(s.isMatch("ab", ".*"));
15+
REQUIRE(s.isMatch("aab", "c*a*b"));
16+
}

‎127. Regular Expression Matching/solution.h

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class Solution {
2+
public:
3+
bool isMatch(const char *s, const char *p) {
4+
for (char c=*p; c != '\0'; ++s, c=*p) {
5+
if (p[1] != '*') ++p;
6+
else if (isMatch(s, p+2)) return true;
7+
if (!(c == *s || (c == '.' && *s != '\0'))) return false;
8+
}
9+
return *s == '\0';
10+
}
11+
};

0 commit comments

Comments
 (0)
0