430，劍指 Offer-動態(tài)規(guī)劃求正則表達(dá)式匹配
問題描述
請實(shí)現(xiàn)一個函數(shù)用來匹配包含'. '和'*'的正則表達(dá)式。模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現(xiàn)任意次（含0次）。在本題中，匹配是指字符串的所有字符匹配整個模式。
例如，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配，但與"aa.a"和"ab*a"均不匹配。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串。
示例 2:
輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因?yàn)?'*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次。
示例?3:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個或多個（'*'）任意字符（'.'）。
示例 4:
輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因?yàn)?'*' 表示零個或多個，這里 'c' 為 0 個, 'a' 被重復(fù)一次。因此可以匹配字符串 "aab"。
示例 5:
輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false
s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母以及字符 . 和 *，無連續(xù)的 '*'。
動態(tài)規(guī)劃求解
這題是劍指offer的第19題，難度是困難。我們也可以看下之前寫的一道和這題非常類似的一道題395，動態(tài)規(guī)劃解通配符匹配問題，今天這題和第395題有一點(diǎn)不同的是，第395題的“*”可以匹配任意字符串，而這題的“*”表示他前面的字符可以出現(xiàn)任意次（包含0次）。
我們先定義一個二維數(shù)組dp，其中dp[i][j]表示的是p的前j個字符和s的前i個字符匹配的結(jié)果。
一，邊界條件
我們默認(rèn)dp[0][0]=true；也就是p的前0個字符和s的前0個字符是可以匹配的。因?yàn)樽址?”表示的是匹配他前面的字符0次或者多次，如果p的字符類似于“a*b*c”，那么字符“*”是可以消去前面的一個字符的。我們就以字符"a*b*c"為例來畫個圖看一下
所以邊界條件的代碼如下
1public?boolean?isMatch(String?s,?String?p)?{
2????if?(s?==?null?||?p?==?null)
3????????return?false;
4????int?m?=?s.length();
5????int?n?=?p.length();
6????boolean[][]?dp?=?new?boolean[m?+?1][n+1];
7????dp[0][0]?=?true;
8????for?(int?i?=?0;?i? 9????????//如果p的第i+1個字符也就是p.charAt(i)是"*"的話，
10????????//那么他就可以把p的第i個字符給消掉（也就是匹配0次）。
11????????//我們只需要判斷p的第i-1個字符和s的前0個字符是否匹
12????????//配即可。比如p是"a*b*"，如果要判斷p的第4個字符
13????????//"*"和s的前0個字符是否匹配，因?yàn)樽址?*"可以消去
14????????//前面的任意字符，只需要判斷p的"a*"和s的前0個字
15????????//符是否匹配即可
16????????if?(p.charAt(i)?==?'*'?&&?dp[0][i?-?1])?{
17????????????dp[0][i?+?1]?=?true;
18????????}
19????}
20????……
21}
邊界條件我們已經(jīng)找到了，下面再來看一下遞推公式。
二，遞推公式
1，如果p的第j+1個字符和s的第i+1個字符相同，或者p的第j+1個字符是“.”（"."可以匹配任意字符），我們只需要判斷p的前j個字符和s的前i個字符是否匹配，這個還好理解，我們畫個圖看一下
p的第3個字符"."是可以和s的第3個字符"f"匹配成功的，我們只需要判斷p的前2個字符和s的前2個字符是否匹配成功即可。
代碼如下
if (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.') {dp[i + 1][j + 1] = dp[i][j];}
2，如果p的第j+1個字符和s的第i+1個字符不能匹配，并且p的第j+1個字符是"*"，那么就要分兩種情況
（1）p的第j個字符和s的第i+1個字符不能匹配，
比如：s="abc"，p="abcd*"
我們就讓p的第j個和第j+1個字符同時消失，也就是讓"d*"消失，只需要判斷p的前j-1個字符和s的前i+1個字符是否匹配即可。
也就是下面這樣
代碼如下
if (p.charAt(j) == '*') {if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {dp[i + 1][j + 1] = dp[i + 1][j - 1];}}
（2）p的第j個字符和s的第i+1個字符匹配成功，有3種情況
類似于s="abc"，p="abcc*";? ?我們就讓*匹配0個，把p的"c*"砍掉，判斷s="abc"和p="abc"是否匹配
dp[i+1][j+1] = dp[i+1][j-1]類似于s="abc"，p="abc*";? ?我們就讓*匹配1個，把p的字符"*"砍掉，判斷s="abc"和p="abc"是否匹配
dp[i+1][j+1] = dp[i+1][j]類似于s="abcc"(或者s="abccc"，s="abcccc"……)，p="abc*";? 我們就讓*匹配多個，把s的最后一個字符"c"砍掉，判斷s="abc"(或者s="abcc"，s="abccc"……)和p="abc*"是否匹配
dp[i+1][j+1] = dp[i][j+1]前面兩個的遞推公式很好理解，關(guān)鍵是第3個為什么要這樣寫。其實(shí)我們可以這樣想，把"c*"看做是一個整體，比如"abccc"的最后一個字符"c"和p的倒數(shù)第二個字符匹配成功，因?yàn)?c*"可以匹配多個，我們就把"abccc"砍掉一個字符"c"，然后再判斷"abcc"和"abc*"是否匹配。
上面三個遞推公式只要有一個為true，就表示能夠匹配成功
我們來看下完整的遞推公式
1if?(p.charAt(j)?==?s.charAt(i)?||?p.charAt(j)?==?'.')?{
2????dp[i?+?1][j+1]?=?dp[i][j];
3}?else?if?(p.charAt(j)?==?'*')?{
4????if?(p.charAt(j?-?1)?!=?s.charAt(i)?&&?p.charAt(j?-?1)?!=?'.')?{
5????????dp[i?+?1]?[j+1]=?dp[i?+?1][j-1];
6????}?else?{
7????????dp[i?+?1][j+1]?=?(dp[i?+?1][j]?||?dp[i][j+1]||?dp[i?+?1][j-1]);
8????}
9}
其實(shí)上面代碼有個重復(fù)的地方就是當(dāng)p的第j+1個字符是"*"的時候，里面的兩種判斷方式都會有一個匹配0個的判斷，我們可以把它提取出來，像下面這樣
1if?(p.charAt(j)?==?s.charAt(i)?||?p.charAt(j)?==?'.')?{
2????dp[i?+?1][j+1]?=?dp[i][j];
3}?else?if?(p.charAt(j)?==?'*')?{
4????//遞歸公式
5????if?(p.charAt(j?-?1)?==?s.charAt(i)?||?p.charAt(j?-?1)?==?'.')?{
6????????dp[i?+?1][j+1]?=?dp[i?+?1]?[j]||?dp[i][j+1];
7????}
8????dp[i?+?1]?[j+1]|=?dp[i?+?1][j-1];
9}
10
實(shí)際上匹配1個和匹配多個也可以合并，代碼如下
1if?(p.charAt(j)?==?s.charAt(i)?||?p.charAt(j)?==?'.')?{
2????dp[i?+?1][j?+?1]?=?dp[i][j];
3}?else?if?(p.charAt(j)?==?'*')?{
4????//遞歸公式
5????if?(p.charAt(j?-?1)?==?s.charAt(i)?||?p.charAt(j?-?1)?==?'.')?{
6????????dp[i?+?1][j?+?1]?=?dp[i][j?+?1];
7????}
8????dp[i?+?1][j?+?1]?|=?dp[i?+?1][j?-?1];
9}
邊界條件和遞推公式都有了，我們再來看下完整代碼
1public?boolean?isMatch(String?s,?String?p)?{
2????if?(s?==?null?||?p?==?null)
3????????return?false;
4????int?m?=?s.length();
5????int?n?=?p.length();
6????boolean[][]?dp?=?new?boolean[m?+?1][n?+?1];
7????dp[0][0]?=?true;
8????for?(int?i?=?0;?i? 9????????//如果p的第i+1個字符也就是p.charAt(i)是"*"的話，
10????????//那么他就可以把p的第i個字符給消掉（也就是匹配0次）。
11????????//我們只需要判斷p的第i-1個字符和s的前0個字符是否匹
12????????//配即可。比如p是"a*b*"，如果要判斷p的第4個字符
13????????//"*"和s的前0個字符是否匹配，因?yàn)樽址?*"可以消去
14????????//前面的任意字符，只需要判斷p的"a*"和s的前0個字
15????????//符是否匹配即可
16????????if?(p.charAt(i)?==?'*'?&&?dp[0][i?-?1])?{
17????????????dp[0][i?+?1]?=?true;
18????????}
19????}
20????for?(int?i?=?0;?i?21????????for?(int?j?=?0;?j?22????????????if?(p.charAt(j)?==?s.charAt(i)?||?p.charAt(j)?==?'.')?{
23????????????????dp[i?+?1][j?+?1]?=?dp[i][j];
24????????????}?else?if?(p.charAt(j)?==?'*')?{
25????????????????//遞歸公式
26????????????????if?(p.charAt(j?-?1)?==?s.charAt(i)?||?p.charAt(j?-?1)?==?'.')?{
27????????????????????dp[i?+?1][j?+?1]?=?dp[i][j?+?1];
28????????????????}
29????????????????dp[i?+?1][j?+?1]?|=?dp[i?+?1][j?-?1];
30????????????}
31????????}
32????}
33????return?dp[m][n];
34}
如果覺得代碼有點(diǎn)長，還可以看個更簡潔的寫法，不過原理都一樣
1public?boolean?isMatch(String?s,?String?p)?{
2????int?m?=?s.length(),?n?=?p.length();
3????boolean[][]?dp?=?new?boolean[m?+?1][n?+?1];
4????dp[0][0]?=?true;
5????for?(int?i?=?0;?i?<=?m;?i++)
6????????for?(int?j?=?1;?j?<=?n;?j++)
7????????????if?(p.charAt(j?-?1)?==?'*')
8????????????????dp[i][j]?=?dp[i][j?-?2]?||?(i?>?0?&&?(s.charAt(i?-?1)?==?p.charAt(j?-?2)?||?p.charAt(j?-?2)?==?'.')?&&?dp[i?-?1][j]);
9????????????else
10????????????????dp[i][j]?=?i?>?0?&&?dp[i?-?1][j?-?1]?&&?(s.charAt(i?-?1)?==?p.charAt(j?-?1)?||?p.charAt(j?-?1)?==?'.');
11????return?dp[m][n];
12}
遞歸求解
先來定義一個函數(shù)，他表示的是s的首字符和p的首字符是否匹配。
1//比較s的首字符和p的首字符是否匹配
2private?boolean?comp(String?s,?String?p)?{
3????return?s.charAt(0)?==?p.charAt(0)?||?p.charAt(0)?==?'.';
4}
如果要判斷字符串s和p是否匹配，我們來看一下遞歸函數(shù)的大致框架
1public?boolean?isMatch(String?s,?String?p)?{
2????if?(p.length()?==?0)?{
3????????return?s.length()?==?0;
4????}
5????if?(p.length()?>?1?&&?p.charAt(1)?==?'*')?{
6????????//?p的第二個字符是?'*'
7????????……
8????}?else?{
9????????//?p的第二個字符不是?'*'
10????????……
11????}
12}
因?yàn)樽址?*"不能單獨(dú)存在，他需要和他前面的字符搭配使用，成為一個組合。
1，當(dāng)p的第二個字符不是"*"的時候，那么p的第一個字符就可以單獨(dú)和s的第一個字符進(jìn)行比較。
2，如果p的第二個字符是"*"，那么p的第二個字符和第一個字符必須成為一個組合來進(jìn)行匹配，也就類收于"a*"。下面會分為兩種情況
字符"*"匹配0次，讓字符"*"和他前面的那個字符同時消失，然后判斷字符串s和p.substring(2)是否匹配。
字符"*"匹配1次或多次，讓字符串s砍掉首字符，然后繼續(xù)和字符串p匹配。
搞懂了上面的過程，代碼就比較簡單了，來看下完整代碼
1public?boolean?isMatch(String?s,?String?p)?{
2????if?(p.length()?==?0)?{
3????????return?s.length()?==?0;
4????}
5????if?(p.length()?>?1?&&?p.charAt(1)?==?'*')?{
6????????//?p的第二個字符是?'*'
7????????//1,字符"*"把前面的字符消掉，也就是匹配0次
8????????//2,字符"*"匹配1次或多次
9????????return?isMatch(s,?p.substring(2))?||?(s.length()?>?0?&&?comp(s,?p))?&&?isMatch(s.substring(1),?p);
10????}?else?{
11????????//?p的第二個字符不是?'*'，判斷首字符是否相同，如果相同再從第二位繼續(xù)比較
12????????return?s.length()?>?0?&&?comp(s,?p)?&&?(isMatch(s.substring(1),?p.substring(1)));
13????}
14}
15
16//比較s的首字符和p的首字符是否匹配
17private?boolean?comp(String?s,?String?p)?{
18????return?s.charAt(0)?==?p.charAt(0)?||?p.charAt(0)?==?'.';
19}
總結(jié)
這題被標(biāo)注為hard，確實(shí)是有一定的難度，使用動態(tài)規(guī)劃應(yīng)該是最容易理解的，關(guān)鍵難點(diǎn)是上面遞推公式的推導(dǎo)
例如漫畫文章
例如講解算法思想的文章
等等，如果你想學(xué)習(xí)算法，學(xué)習(xí)計算機(jī)基礎(chǔ)，那么我決定這份 PDF，一定會讓你有所幫助。當(dāng)然，如果一是一位有那么點(diǎn)迷茫的在校生，相信我的個人經(jīng)歷，可以給你打一份雞血，讓你更好著去尋找自己的目標(biāo)。
文章整體目錄
如何獲取
很簡單，在我的微信公眾號?帥地玩編程?回復(fù)?程序員內(nèi)功修煉?即可獲取《程序員內(nèi)功修煉》第一版和第二版的 PDF。