给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

1
2
3
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

1
2
3
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：

1
2
3
输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：

1
2
输入：s = "mississippi" p = "mis*is*p*."
输出：false

提示：

1
2
3
4
5
0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

这道理挺有意思。一开始的思路其实和解法相近，但是有一个地方想错了，就是 .*的*是可以匹配任意多个’.‘，而不是匹配一个常量字符。脑回路蠢的可以。下面说下思路：

  • 首先判断s[i]和p[j]是否相等。如果相等的话，判断p的下一个字符是否是星号。如果是星号，那么s第i个位之前的字符已经匹配成功，那么就判断s[i+1]和p是否匹配，这里为啥是p[j:]而不是p[j+1:]呢，因为*可以匹配前面0个字符呀，所以p[j+1:]用于递归才是合理的。如果不是星号，那么就判断s[i+1]和p[j+1]是否匹配；
  • 如果s[i]和p[j]不相等的话，那么判断p[j+1]是否是星号，如果是星号，那么判断s[i]和p[j+2]是否匹配；如果不是星号，那么就肯定不匹配了。
  • 判断递归终止条件，这往往是最难的一步，可以根据逻辑推导下；
  • 注意substr的时候不要越界。

此外还需要注意的是，下面代码中的s.substr(1)是不会错的！所以不用考虑越界问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;

bool match(string s, string p){
    if(s.length()==0) return p.length()==0;
    auto isEq =s.length()>0 && (s[0]==p[0] || p[0]=='.');
    if(p.length()>=2 && p[1]=='*'){
        return (isEq && match(s.substr(1),p) || match(s,p.substr(2)));
    }else{
        return isEq && match(s.substr(1),p.substr(1));
    }
}

int main(){
    cout<<match("a",".")<<endl;
    string s = "a";
    cout<<s.substr(1)<<endl;
    
    return 0;
}

参考：

allen在该题下的题解，Allen主页。