本文为剑指 offer 系列第四十九篇。
这个题目比较难，甚至我觉得是整个剑指offer里面最难的一道题目了，
也是参考了网上的答案加上自己的理解来解决这道题目，no more talk, show you code!
请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
解题思路
本题目其实关注的点比较多，下面一个一个来说
- 匹配串或者模式串为空的情况
- 字符串是以’\0’为标志结束的
- **.**的处理，可以表示任何一个字符,要注意此时匹配串是不是已经到了结尾
- 号的处理，由于可以表示它前面的字符出现0次，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
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public:
bool match(char* str, char* pattern)
{
// 两者任意一个为空，则返回空。
if(str == NULL || pattern == NULL){
return false;
}
return matchCore(str, pattern);
}
//本部分以str = aaa 为例进行说明。
bool matchCore(char* str, char* pattern){
// 字符串和模式串都运行到了结尾，则匹配完成。返回true
if(*str == '\0' && *pattern == '\0'){
return true;
}
// 字符串没有到结尾，模式串到结尾了，则返回false
// 模式串没有到结尾，字符串到结尾了，则根据后续判断进行，需要对'*'做处理
if((*str != '\0' && *pattern == '\0')){
return false;
}
// 如果模式串的下一个字符是'*'，
if(*(pattern + 1) == '*'){
// 如果字符串和模式串相等，或者模式串是'.'，并且字符串没有到结尾，则继续匹配
if(*str == *pattern || (*pattern == '.' && *str != '\0')){
// 可能存在三种情况。
// 1. *匹配前面字符0次， 如pattern = a*aaa
// 2. *匹配前面字符1次， 如pattern = a*aa
// 3. *匹配前面字符不止一次，如pattern = a*
return // *匹配0次
matchCore(str, pattern + 2)||
// *匹配1次
matchCore(str + 1, pattern + 2) ||
// *匹配不止1次
matchCore(str + 1, pattern);
}
// 如果字符串和模式串不相等，则跳过当前模式串的字符和'*'，进入新一轮的匹配
else{
// 比如pattern = b*aaa
return matchCore(str, pattern + 2);
}
}
// 如果字符串和模式串相等，或者模式串是'.'，并且字符串没有到结尾，则继续匹配
if(*str == *pattern || (*pattern == '.' && *str != '\0')){
return matchCore(str + 1, pattern + 1);
}
return false;
}
};
|
以上，本题结束！