《正则表达式匹配》在Leetcode属于难度为Hard的问题，我自己花了半天，使用递归的方式完成了题目，但是程序效率很低。后来看了“标准答案”，花了一些时间研究才完全理解，这篇文章我尝试解释“标准答案”使用的算法。
问题
给出一个字符串(s)和一个表达式(p)，实现一个支持'.'和''正则表达式的匹配。
'.' 匹配任意单个字符
'*' 匹配0个或多个前一个字符
表达式必须匹配整个字符串而不是其中一部分
Note：
- s 可以为空或非空字符串，字符串中字符的取值范围为 a-z
- p 可以为空或非空字符串，字符串中字符的取值范围为 a-z, 还可以包含两个特殊字符"."和"*”
例1：
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
例2：
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
例3：
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
例4：
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
例5：
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
“标准答案”算法
- 构造一个二维数组dp
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
- 初始化dp
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
- 遍历字符串s和字符串p中的字符
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
// 该字符匹配成功，使用去掉1个字符的s子串和p子串的匹配结果，作为当前子串的匹配结果
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
// 该字符匹配成功，使用去掉1个字符的s子串和p子串的匹配结果，作为当前子串的匹配结果
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
// 如果遇到 '*'
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
// 该字符和p中上一个字符匹配失败，使用当前s子串和去掉2个字符的p子串的匹配结果，作为当前子串的匹配结果
dp[i+1][j+1] = dp[i+1][j-1];
} else {
// 该字符和p中上一个字符匹配成功，使用下面三个匹配结果作与运算后的结果，作为当前子串的匹配结果
// 1. s子串去掉一个字符，和当前p子串的匹配结果 （in this case, a* counts as multiple a ）
// 2. s子串和p子串去掉1个字符的匹配结果（in this case, a* counts as single a）
// 3. s子串和p子串去掉2个字符的匹配结果（in this case, a* counts as empty）
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
- 返回最终结果
return dp[s.length()][p.length()];
概述
该算法的核心是，通过二维遍历，依次计算所有s子串和p子串的匹配结果，最后的匹配结果，就是整个s串和p串的匹配结果
假设 s="xaabyc" p="xa*b.c"
1，初始化
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
- 空串和空串匹配，结果为True，所以 dp[0][0] = true
| s\p | 0 | x | a | * | b | . | c |
|---|---|---|---|---|---|---|---|
| 0 | T | F | F | F | F | F | F |
| x | F | ||||||
| a | F | ||||||
| a | F | ||||||
| b | F | ||||||
| y | F | ||||||
| c | F |
2，遍历字符串s和字符串p中的字符
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
// 该字符匹配成功，使用去掉1个字符的s子串和p子串的匹配结果，作为当前子串的匹配结果
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
// 该字符匹配成功，使用去掉1个字符的s子串和p子串的匹配结果，作为当前子串的匹配结果
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
// 如果遇到 '*'
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
// 该字符和p中上一个字符匹配失败，使用当前s子串和去掉2个字符的p子串的匹配结果，作为当前子串的匹配结果
dp[i+1][j+1] = dp[i+1][j-1];
} else {
// 该字符和p中上一个字符匹配成功，使用下面三个匹配结果作与运算后的结果，作为当前子串的匹配结果
// 1. s子串去掉一个字符，和当前p子串的匹配结果 （in this case, a* counts as multiple a ）
// 2. s子串和p子串去掉1个字符的匹配结果（in this case, a* counts as single a）
// 3. s子串和p子串去掉2个字符的匹配结果（in this case, a* counts as empty）
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
Loop1：i=1, j=1 to 6
- s[1] = 'x', j[1] = 'x'
- s[1] == j[1], 所以 dp[1][1] = dp[0][0]，结果为True
- s[1] != j[2,3,4,5,6] 所以 dp[1][2,3,4,5,6] = False
| s\p | 0 | x | a | * | b | . | c |
|---|---|---|---|---|---|---|---|
| 0 | T | F | F | F | F | F | F |
| x | F | T | F | F | F | F | F |
| a | F | ||||||
| a | F | ||||||
| b | F | ||||||
| y | F | ||||||
| c | F |
Loop2：i=2, j=1 to 6
- 当 i = 2, j = 3 是，s[i] = 'a', p[j] = '*'
- 这个时候s的子串 “xa” 既匹配 "xa"，也匹配 "xa*"
- 所以 dp[2][2] = True, dp[2][3] = True
| s\p | 0 | x | a | * | b | . | c |
|---|---|---|---|---|---|---|---|
| 0 | T | F | F | F | F | F | F |
| x | F | T | F | F | F | F | F |
| a | F | F | T | T (注意) | F | F | F |
| a | F | ||||||
| b | F | ||||||
| y | F | ||||||
| c | F |
后面的逻辑依次类推，最后得出最终结果如下
| s\p | 0 | x | a | * | b | . | c |
|---|---|---|---|---|---|---|---|
| 0 | T | F | F | F | F | F | F |
| x | F | T | F | F | F | F | F |
| a | F | F | T | T | F | F | F |
| a | F | F | F | T | F | F | F |
| b | F | F | F | F | T | F | F |
| y | F | F | F | F | F | T | F |
| c | F | F | F | F | F | F | T (最终结果) |
网友评论