我現(xiàn)在在做一個(gè)叫《leetbook》的開(kāi)源書(shū)項(xiàng)目橱赠，把解題思路都同步更新到github上了督惰，需要的同學(xué)可以去看看
地址：https://github.com/hk029/leetcode
這個(gè)是書(shū)的地址：https://hk029.gitbooks.io/leetbook/
這里寫(xiě)圖片描述
- Regular Expression Matching
問(wèn)題
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a") → true
isMatch("aa", ".") → true
isMatch("ab", ".") → true
isMatch("aab", "ca*b") → true
思路
<font size=4>這里面最復(fù)雜的操作是"*"鸳兽，這是個(gè)很可惡的操作服球，因?yàn)槟阌肋h(yuǎn)不知道它多長(zhǎng)挖诸。但是有一點(diǎn)任柜，"*"不會(huì)單獨(dú)出現(xiàn)枫笛，它一定是和前面一個(gè)字母或"."配成一對(duì)吨灭。看成一對(duì)后"X*"刑巧，它的性質(zhì)就是：要不匹配0個(gè)喧兄，要不匹配連續(xù)的“X”
<font size=4>題目的關(guān)鍵就是如何把這一對(duì)放到適合的位置。
<font size=4>考慮一個(gè)特殊的問(wèn)題：
<font size=4>情況1：
“aaaaaaaaaaaaaaaa"
"aaa"
<font size=4>情況2：
“aaaaaaaaaaaaaaaa"
"aab"
<font size=4>在不知道后面的情況的時(shí)候啊楚，我如何匹配a*吠冤？
<font size=4>最長(zhǎng)匹配
<font size=4>顯然不合適，這樣后面的a就無(wú)法匹配上了<font size=4> 匹配到和后面長(zhǎng)度一樣的位置恭理，比如情況1拯辙，就是留3個(gè)a不匹配，讓后面3個(gè)字母嘗試去匹配颜价。
這樣看似合適涯保，但是遇到情況2就不行了饵较。<font size=4>回溯，每種"*"的情況遭赂，看哪種情況能成功循诉，如果其中出現(xiàn)了問(wèn)題，馬上回溯撇他，換下一種情況
思路1——回溯
<font size=4>如果“*”不好判斷茄猫，那我大不了就來(lái)個(gè)暴力的算法，把“”的所有可能性都測(cè)試一遍看是否有滿(mǎn)足的困肩，用兩個(gè)指針i,j來(lái)表明當(dāng)前s和p的字符划纽。
我們采用<font color=red>從后往前匹配</font>，為什么這么匹配锌畸，<font color=blue>因?yàn)槿绻覀儚那巴笃ヅ溆铝樱總€(gè)字符我們都得判斷是否后面跟著“”，而且還要考慮越界的問(wèn)題潭枣。但是從后往前沒(méi)這個(gè)問(wèn)題比默，一旦遇到“*”，前面必然有個(gè)字符盆犁。</font>
- <font size=4>如果j遇到"*"命咐，我們判斷s[i] 和 p[j-1]是否相同，
- <font size=4>如果相同我們可以先嘗試匹配掉s的這個(gè)字符谐岁，i--醋奠，然后看之后能不能滿(mǎn)足條件，滿(mǎn)足條件伊佃，太棒了窜司！我們就結(jié)束了，如果中間出現(xiàn)了一個(gè)不滿(mǎn)足的情況航揉，馬上回溯到不匹配這個(gè)字符的狀態(tài)塞祈。
- <font size=4>不管相同不相同，都不匹配s的這個(gè)字符迷捧，j-=2 (跳過(guò)“*”前面的字符)
if(p[j-1] == '.' || p[j-1] == s[i])
if(myMatch(s,i-1,p,j))
return true;
return myMatch(s,i,p,j-2);
- <font size=4>如果j遇到的不是“*”织咧，那么我們就直接看s[i]和p[j]是否相等，不相等就說(shuō)明錯(cuò)了漠秋，返回。
if(p[j] == '.' || p[j] == s[i])
return myMatch(s,i-1,p,j-1);
else return false;
- <font size=4> 再考慮退出的情況
- <font size=4>如果j已經(jīng)<0了說(shuō)明p已經(jīng)匹配完了抵屿，這時(shí)候庆锦，如果s匹配完了，說(shuō)明正確轧葛，如果s沒(méi)匹配完搂抒，說(shuō)明錯(cuò)誤艇搀。
- <font size=4>如果i已經(jīng)<0了說(shuō)明s已經(jīng)匹配完，這時(shí)候求晶，s可以沒(méi)匹配完焰雕，只要它還有"*"存在，我們繼續(xù)執(zhí)行代碼芳杏。
<font size=4>所以代碼應(yīng)該是這樣的：
class Solution {
public:
static const int FRONT=-1;
bool isMatch(string s, string p) {
return myMatch(s,s.length()-1,p,p.length()-1);
}
bool myMatch(string s, int i, string p,int j)
{
if(j == FRONT)
if(i == FRONT) return true;
else return false;
if(p[j] == '*')
{
if(i > FRONT && (p[j-1] == '.' || p[j-1] == s[i]))
if(myMatch(s,i-1,p,j))
return true;
return myMatch(s,i,p,j-2);
}
if(p[j] == '.' || p[j] == s[i])
return myMatch(s,i-1,p,j-1);
return false;
}
};
思路2——DP
<font size=4>DP的話(huà)矩屁，肯定要用空間換時(shí)間了，這里用 monkeyGoCrazy 的思路：用2維布爾數(shù)組爵赵，dp[i][j]的含義是s[0-i] 與 s[0-j]是否匹配吝秕。
- p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1]
- If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
- If p.charAt(j) == '':
here are two sub conditions:
- if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a only counts as empty
- if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a
dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
<font size=4>這里用的bool數(shù)組比較巧妙，初始化為true空幻。前兩種情況好理解烁峭，如果匹配成功就維持之前的真假值。程序的目的是看真值能不能傳遞下去秕铛。如果遇到三種情況约郁，我們就看哪種情況有真值可以傳遞，就繼續(xù)傳遞下去但两。
圖示
<font size=4>我用excel自己跑了下代碼棍现，畫(huà)了一下示意圖，下面橘黃色表示正常匹配了镜遣，藍(lán)色表示“*”匹配空串己肮。可以看出真值是如何傳遞下去的悲关。
初始化
dp[0][0] = true;
//初始化第0行,除了[0][0]全為false谎僻，毋庸置疑，因?yàn)榭沾畃只能匹配空串寓辱，其他都無(wú)能匹配
for (int i = 1; i <= m; i++)
dp[i][0] = false;
//初始化第0列艘绍，只有X*能匹配空串，如果有*秫筏，它的真值一定和p[0][j-2]的相同（略過(guò)它之前的符號(hào)）
for (int j = 1; j <= n; j++)
dp[0][j] = j > 1 && '*' == p[j - 1] && dp[0][j - 2];
代碼執(zhí)行
for(int i = 1;i <= m;i++)
{
for(int j = 1;j <= n;j++)
{
//這里j-1才是正常字符串中的字符位置
//要不*當(dāng)空诱鞠，要不就只有當(dāng)前字符匹配了*之前的字符，才有資格傳遞dp[i-1][j]真值
if(p[j-1] == '*')
dp[i][j] = dp[i][j-2] || (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j];
else
//只有當(dāng)前字符完全匹配这敬，才有資格傳遞dp[i-1][j-1] 真值
dp[i][j] = (p[j-1] == '.' || s[i-1] == p[j-1]) && dp[i-1][j-1];
}
}
返回值
return dp[m][n]
完整代碼
class Solution
{
public:
static const int FRONT=-1;
bool isMatch(string s, string p)
{
int m = s.length(),n = p.length();
bool dp[m+1][n+1];
dp[0][0] = true;
//初始化第0行,除了[0][0]全為false航夺，毋庸置疑，因?yàn)榭沾畃只能匹配空串崔涂，其他都無(wú)能匹配
for (int i = 1; i <= m; i++)
dp[i][0] = false;
//初始化第0列阳掐，只有X*能匹配空串，如果有*，它的真值一定和p[0][j-2]的相同（略過(guò)它之前的符號(hào)）
for (int j = 1; j <= n; j++)
dp[0][j] = j > 1 && '*' == p[j - 1] && dp[0][j - 2];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (p[j - 1] == '*')
{
dp[i][j] = dp[i][j - 2] || (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j];
}
else //只有當(dāng)前字符完全匹配缭保，才有資格傳遞dp[i-1][j-1] 真值
{
dp[i][j] = (p[j - 1] == '.' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
