手寫了一個正則表達式引擎：遞歸、動態規劃
大家好，我是小風哥，這是 LeetCode 刷題系列第 6 篇。
今天的題目是手寫正則表達式匹配，要求是這樣的：給定字符串 s 以及模式 p，實現支持‘.’和'*'的正則表達式匹配。
-
'.'匹配任何單個字符
-
'*'匹配 0 個或者多個前一個字符
示例：
輸入: s = "aa", p = "a*"
輸出: true
解釋: '*'匹配0個或者多個前一個字符，也就是字符'a'. 因此重複一次就變成了"a".在往下看之前先想一想這個題目。
千萬不要把這個問題想得太複雜，用 6 行 C++ 代碼即可解決，我們先來分析一下。
從最簡單的情況開始考慮。
如果給定的模式中沒有星號 "*"，那麼問題再簡單不過，可以使用遞歸函數輕鬆搞定（關於遞歸這個話題後續會有文章詳細講解）：
bool is_match(string& s, int bs, string&p, int bp) {
if (bp == p.length()) return bs == s.length();
bool is_first_match = (bs < s.length()) &&(s[bs] == p[bp] || p[bp] == '.');
return is_first_match && is_match(s, bs+1, p, bp+1);
}可以看到，真正的邏輯只有 3 行代碼，其中參數 bs、bp 表示字符串 s 和模式 p 的起始下標，我們需要做的僅僅是判斷當前字符 s[bs] 與模式中的字符 p[bp] 是否匹配，這分爲兩種情況：
-
兩個字符嚴格相同，（圖中的 ^ 表示省略）
-
模式中的當前字符爲‘.’，因爲‘.’可以匹配任意字符
這一部分的代碼就一句話：
bool is_first_match = (bs < s.length()) &&(s[bs] == p[bp] || p[bp] == '.');當前字符匹配後還要判斷後面的子字符串是否也匹配：
is_match(s, bs+1, p, bp+1)這樣最簡單的情況就考慮完畢。
接下來想要考慮星號，注意，這個題目最爲關鍵是你必須意識到：
如果後一個字符是星號 ""，那麼你需要將當前字符與星號 “” 作爲一個整體來考慮，而不能簡單根據當前字符是否是星號來思考，再次強調，因爲它們是一個整體
如果下一個字符爲星號該怎麼辦呢？
星號的作用有兩個，一個是表示重複前一個字符 0 次，也就是說在這種情況下我們可以把當前字符與星號全部忽略掉，因此我們的 bp 可以直接往後移動 2 個位置去計算下一個子問題：
用代碼表示就是：
is_match(s, bs, p, bp+2)我們說過星號的作用有兩個，一個是表示重複前一個字符 0 次；另一個是可以重複任意次，在後一種情況下就要求模式中的前一個字符必須和字符串中的當前字符匹配纔可以，比如上圖中字符串和模式中的字符都是 a，因此我們可以重複使用 “a*” 一次，這樣 bp 指針無需移動只需要 bs 加 1 即可，表示重複使用一次：
用代碼表示就是：
isfirstmatch && is_match(s, bs+1, p, bp);這樣完整的代碼呼之欲出：
bool is_match(string& s, int bs, string&p, int bp) {
if (bp == p.length()) return bs == s.length();
bool isfirstmatch = (bs < s.length()) &&(s[bs] == p[bp] || p[bp] == '.');
if (bp < p.length() - 1 && p[bp + 1] == '*') {
return is_match(s, bs, p, bp+2) || isfirstmatch && is_match(s, bs+1, p, bp);
} else {
return isfirstmatch && is_match(s, bs+1, p, bp+1);
}
}可以看到，真正的邏輯只有 6 行，你就實現了一個正則表達式引擎。
仔細看上述代碼，實際上該代碼包含最優子結構（關於動態規劃與最優子結構這個話題後續會有文章詳細講解），因此我們可以使用動態規劃代碼來解決。
在動態規劃版中我們同樣遵循一個原則，即：
如果後一個字符是星號 ""，那麼你需要將當前字符與星號 “” 作爲一個整體來考慮，而不能簡單根據當前字符是否是星號來思考，再次強調，因爲它們是一個整體
我們規定：
dp[i][j] 表示文本 0-i 是否和模式 0-j 匹配
如果當前字符的下一個字符不是星號則：
dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i-1][j-1];而如果當前字符的下一個字符是星號那麼：
dp[i][j] = dp[i][j-1] || ((s[i] == p[j]||p[j]=='.')&& dp[i-1][j]);這樣遞推表達式寫出後剩下的就簡單啦：
bool isMatchdp(string s, string p) {
int lens = s.length();
int lenp = p.length();
s = "0" + s;
p = "0" + p;
vector<vector<bool>> dp(lens+1, vector<bool>(lenp+1, false));
dp[0][0]=true;
for (int j = 1; j <= lenp;j++) {
if (j % 2 == 0 && p[j] == '*') {
dp[0][j-1] = dp[0][j] = dp[0][j-2];
}
}
for (int i = 1; i <= lens; i++) {
for (int j = 1; j <= lenp; j++) {
if (p[j] == '*') {
dp[i][j] = dp[i][j-1];
} else if (j != lenp && p[j+1] == '*') {
dp[i][j] = dp[i][j-1] || ((s[i] == p[j]||p[j]=='.')&& dp[i-1][j]);
} else {
dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i-1][j-1];
}
}
}
return dp[lens][lenp];
}代碼逐行詳解
1， 可以看到代碼中有這樣兩行定義：
s = "0" + s;
p = "0" + p;這兩行的作用是什麼呢？
小風哥比較懶，在每個字符串前面加上 “0” 不會改變最終的結果，但是可以在接下來的循環中少一些 corner case 的判斷，因爲地推式中有這樣的代碼：
dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i-1][j-1];如果 i 或者 j 爲 0，那麼減 1 後會變成負值，這顯然會有問題
2， 有了 1 後定義 dp 數組時需要多定義 1 個
vector<vector<bool>> dp(lens+1, vector<bool>(lenp+1, false));3， 同樣因爲 1，我們知道 dp[0][0]一定爲 true，因爲 “0” 和“0”是匹配的。
4， 比較關鍵的是初始化部分的一段代碼：
for (int j = 1; j <= lenp;j++) {
if (j % 2 == 0 && p[j] == '*') {
dp[0][j-1] = dp[0][j] = dp[0][j-2];
}
}假如給定的輸入 s 是空字符串，而模式 p 不是：
s: 0
p: 0a*b*c*我們知道 dp(0,0) 爲 true(“0” 和 "0" 匹配)，dp(0,1) 與 dp(0,2) 也應該爲 true，因爲 a * 可以匹配空字符串，同理 dp(0,3) 與 dp(0,4) 的值也爲 true，因爲 b * 也可以匹配空字符串，但 dp(0,3) 與 dp(0,4) 也要同時依賴 dp(0,2)，因爲如果是這樣的輸入：
s: 0
p: 0acb*c*這時儘管 b * 同樣可以匹配空字符串，但 ac 無法匹配空字符串，因此 dp(0,3) 與 dp(0,4) 的值爲 false
5， 剩下的 for 循環遵循之前給出的遞推時，只需要注意一點：
如果後一個字符是星號 ""，那麼你需要將當前字符與星號 “” 作爲一個整體來考慮，而不能簡單根據當前字符是否是星號來思考，再次強調，因爲它們是一個整體
因此如果當前字符的下一個字符是星號，那麼 dp(i,j) 的值等於 dp(i,j-1) 即可：
for (...) {
for (...) {
if (p[j] == '*') {
dp[i][j] = dp[i][j-1];
} else ...
}
}怎麼樣，看上去比較簡單的問題用了 3000 + 字來講解，你學會了嗎？歡迎大家關注小風算法，讓我們去發現去欣賞數據結構與算法之美。
小風哥之前在我的另一個號 “碼農的荒島求生” 中講解的計算機底層文章已經全部彙總在了這裏:https://github.com/xfenglu/everycodershouldknow, 歡迎 star 提 issue。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/7Jx8mtuM7qep_D5iGEDCqg