10\. 正则表达式匹配
# 10. 正则表达式匹配 (opens new window)
# Description
Difficulty: 困难
Related Topics: 递归 (opens new window), 字符串 (opens new window), 动态规划 (opens new window)
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 **整个 **字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
1
2
3
2
3
示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
1
2
3
2
3
示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
1
2
3
2
3
提示：
1 <= s.length <= 201 <= p.length <= 30s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
# Solution
Language: JavaScript
/**
* @param {string} s
* @param {string} p
* @return {boolean}
* 方法1.动态规划
*/
//dp[i][j]表示s的前i个字符能否和p的前j个字符匹配
const isMatch = (s, p) => {
if (s == null || p == null) return false;//极端情况 s和p都是空 返回false
const sLen = s.length, pLen = p.length;
const dp = new Array(sLen + 1);//因为位置是从0开始的，第0个位置是空字符串 所以初始化长度是sLen + 1
for (let i = 0; i < dp.length; i++) {//初始化dp数组
dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false
}
// base case s和p第0个位置是匹配的
dp[0][0] = true;
for (let j = 1; j < pLen + 1; j++) {//初始化dp的第一列，此时s的位置是0
//情况1:如果p的第j-1个位置是*，则j的状态等于j-2的状态
//例如：s='' p='a*' 相当于p向前看2个位置如果匹配，则*相当于重复0个字符
if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
}
// 迭代
for (let i = 1; i < sLen + 1; i++) {
for (let j = 1; j < pLen + 1; j++) {
//情况2:如果s和p当前字符是相等的 或者p当前位置是. 则当前的dp[i][j] 可由dp[i - 1][j - 1]转移过来
//当前位置相匹配，则s和p都向前看一位 如果前面所有字符相匹配 则当前位置前面的所有字符也匹配
//例如：s='XXXa' p='XXX.' 或者 s='XXXa' p='XXXa'
if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == "*") {//情况3:进入当前字符不匹配的分支 如果当前p是* 则有可能会匹配
//s当前位置和p前一个位置相同 或者p前一个位置等于. 则有三种可能
//其中一种情况能匹配 则当前位置的状态也能匹配
//dp[i][j - 2]：p向前看2个位置，相当于*重复了0次，
//dp[i][j - 1]：p向前看1个位置，相当于*重复了1次
//dp[i - 1][j]：s向前看一个位置，相当于*重复了n次
//例如 s='XXXa' p='XXXa*'
if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {
dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
} else {
//情况4:s当前位置和p前2个位置不匹配，则相当于*重复了0次
//例如 s='XXXb' p='XXXa*' 当前位置的状态和p向前看2个位置的状态相同
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[sLen][pLen]; // 长为sLen的s串 是否匹配 长为pLen的p串
};
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
50
51
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
50
51
定义状态：
dp[i][j] 表示 s[1...j] 和 p[1...j] 是否匹配
初始状态：
dp[i][j] = false // 0 < i < s.length ; 0 < j < p.length
dp[0][0] = true
dp[0][j] = dp[0][j-2] && p[j] === '*' // 消除 p 前面无用的字符串
1
2
3
2
3
状态转移方程：
如果
s[i]与p[j]匹配 (s[i] === p[j] || p[j] === '.')
dp[i][j] = dp[i-1][j-1]
如果
p[j] === '*'需要看s[i]与p[j-1]是否匹配
s[i]与p[j-1]不匹配，p[j] === *
dp[i][j] = dp[i][j-2]
s[i]与p[j-1]匹配p[j-1] === s[i] || p[j-1] === '.'
可匹配0次，1次，多次
dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j]
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
// 预处理 s 和 p，让字母下标从 1 开始。
s = ' ' + s;
p = ' ' + p;
// dp[i][j] 表示 s[1...i] 和 p[1...j] 是否匹配
const dp = new Array(s.length).fill(false).map(() => new Array(p.length).fill(false));
// 初始状态
dp[0][0] = true;
// const s = "aab";
// const p = "c*a*b";
// 消除 p 前面无用的字符
for(let i = 1; i < p.length; i++) {
if(p[i] === '*') {
dp[0][i] = dp[0][i-2];
}
}
for(let i = 1; i < s.length; i++) {
for(let j = 1; j < p.length; j++) {
if(p[j] === '.' || s[i] === p[j]) {
dp[i][j] = dp[i-1][j-1];
}
else if(p[j] === '*') {
if(p[j-1] !== s[i] && p[j-1] !== '.') {
dp[i][j] = dp[i][j-2];
}
else {
dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
}
}
}
}
// console.log(dp);
return dp[s.length - 1][p.length - 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
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
var isMatch = function(s, p) {
p = '^' + p + '$'
let reg = new RegExp(p, 'g')
return reg.test(s)
}
var isMatch = function(s, p) {
p = new RegExp(p)
s = s.replace(p, '')
return s === '' ? true : false
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11