《正則表達(dá)式匹配》在Leetcode屬于難度為Hard的問(wèn)題褒傅，我自己花了半天，使用遞歸的方式完成了題目粪躬，但是程序效率很低担败。后來(lái)看了“標(biāo)準(zhǔn)答案”，花了一些時(shí)間研究才完全理解镰官，這篇文章我嘗試解釋“標(biāo)準(zhǔn)答案”使用的算法提前。
問(wèn)題
給出一個(gè)字符串(s)和一個(gè)表達(dá)式(p)，實(shí)現(xiàn)一個(gè)支持'.'和''正則表達(dá)式的匹配泳唠。
'.' 匹配任意單個(gè)字符
'*' 匹配0個(gè)或多個(gè)前一個(gè)字符
表達(dá)式必須匹配整個(gè)字符串而不是其中一部分
Note：
- s 可以為空或非空字符串狈网，字符串中字符的取值范圍為 a-z
- p 可以為空或非空字符串，字符串中字符的取值范圍為 a-z, 還可以包含兩個(gè)特殊字符"."和"*”
例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
“標(biāo)準(zhǔn)答案”算法
- 構(gòu)造一個(gè)二維數(shù)組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個(gè)字符的s子串和p子串的匹配結(jié)果拓哺，作為當(dāng)前子串的匹配結(jié)果
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
// 該字符匹配成功株旷，使用去掉1個(gè)字符的s子串和p子串的匹配結(jié)果沼侣，作為當(dāng)前子串的匹配結(jié)果
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中上一個(gè)字符匹配失敗，使用當(dāng)前s子串和去掉2個(gè)字符的p子串的匹配結(jié)果豪治，作為當(dāng)前子串的匹配結(jié)果
dp[i+1][j+1] = dp[i+1][j-1];
} else {
// 該字符和p中上一個(gè)字符匹配成功谆级，使用下面三個(gè)匹配結(jié)果作與運(yùn)算后的結(jié)果烤礁，作為當(dāng)前子串的匹配結(jié)果
// 1. s子串去掉一個(gè)字符，和當(dāng)前p子串的匹配結(jié)果 （in this case, a* counts as multiple a ）
// 2. s子串和p子串去掉1個(gè)字符的匹配結(jié)果（in this case, a* counts as single a）
// 3. s子串和p子串去掉2個(gè)字符的匹配結(jié)果（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]);
}
}
}
}
- 返回最終結(jié)果
return dp[s.length()][p.length()];
概述
該算法的核心是肥照，通過(guò)二維遍歷脚仔，依次計(jì)算所有s子串和p子串的匹配結(jié)果，最后的匹配結(jié)果舆绎，就是整個(gè)s串和p串的匹配結(jié)果
假設(shè) 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;
}
}
- 空串和空串匹配，結(jié)果為T(mén)rue亿蒸，所以 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個(gè)字符的s子串和p子串的匹配結(jié)果边锁，作為當(dāng)前子串的匹配結(jié)果
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
// 該字符匹配成功姑食，使用去掉1個(gè)字符的s子串和p子串的匹配結(jié)果，作為當(dāng)前子串的匹配結(jié)果
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中上一個(gè)字符匹配失敗茅坛，使用當(dāng)前s子串和去掉2個(gè)字符的p子串的匹配結(jié)果音半，作為當(dāng)前子串的匹配結(jié)果
dp[i+1][j+1] = dp[i+1][j-1];
} else {
// 該字符和p中上一個(gè)字符匹配成功则拷，使用下面三個(gè)匹配結(jié)果作與運(yùn)算后的結(jié)果，作為當(dāng)前子串的匹配結(jié)果
// 1. s子串去掉一個(gè)字符曹鸠，和當(dāng)前p子串的匹配結(jié)果 （in this case, a* counts as multiple a ）
// 2. s子串和p子串去掉1個(gè)字符的匹配結(jié)果（in this case, a* counts as single a）
// 3. s子串和p子串去掉2個(gè)字符的匹配結(jié)果（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]煌茬，結(jié)果為T(mén)rue
- 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
- 當(dāng) i = 2, j = 3 是，s[i] = 'a', p[j] = '*'
- 這個(gè)時(shí)候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 |
后面的邏輯依次類(lèi)推坛善，最后得出最終結(jié)果如下
| 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 (最終結(jié)果) |
