引子

思路：看到兩個(gè)序列去匹配的問題鹦牛，最自然的想法是雙層循環(huán)嘗試對(duì)齊匹配，我們假設(shè)表格數(shù)字為1代表匹配成功勇吊，0代表匹配失敗曼追。

圖1

分析：分別遍歷s和p兩個(gè)字符串，如果p[i] == s[j]汉规，則表示匹配成功礼殊，否則直接退出循環(huán)遍歷。
用代碼也很好實(shí)現(xiàn)

bool isMatch(char * s, char * p){
    int n = strlen(s);
    int m = strlen(p);
    int dp[m][n];
    
    for(int i = 0; i < m; I++)
        for(int j = 0; j < n; j++)
            dp[i][j] = 0;
    
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if (s[j] == p[I])
                dp[i][j] = 1;
            else
                return false;
        }
    }
    return dp[m][n];
}

但是针史，事實(shí)并不會(huì)這樣簡(jiǎn)單晶伦，因?yàn)橛刑厥夥?hào)星號(hào)('*')和問號(hào)('?')的加入，讓事情變得復(fù)雜啄枕。細(xì)致分析的話可能情況很多已經(jīng)無從下手了婚陪。

1、s 和 p 都為空

既然無從下手射亏，我們就用最笨的辦法近忙，從最簡(jiǎn)單的方法逐步去逼近自然的情況竭业，自然智润，最簡(jiǎn)單的情況當(dāng)然是 p 和 s 均為空了。

圖2

分析：兩個(gè)都為空未辆，是匹配成功的窟绷。
結(jié)論：匹配成功

2、p為空

假設(shè) p = ''咐柜， s = 'abcd'兼蜈，將情況1中融合進(jìn)去

圖3

分析：當(dāng) p 為空時(shí)攘残，
1、如果 s 為空的時(shí)候为狸，匹配成功
2歼郭、如果 s 非空的時(shí)候，匹配失敗
結(jié)論：匹配失敗

3辐棒、s為空

如果拿上例來類推的話病曾，會(huì)理所當(dāng)然的認(rèn)為：
當(dāng) s 為空時(shí)，
1漾根、如果 p 為空的時(shí)候泰涂，匹配成功
2、如果 p 非空的時(shí)候辐怕，匹配失敗
對(duì)于情況1逼蒙，當(dāng)然沒有疑問了；對(duì)于情況2寄疏，如果沒有星號(hào)('*')是牢、問號(hào)('?')特殊符號(hào)搗亂的話，確實(shí)也會(huì)匹配失敗赁还，但如果考慮星號(hào)('*')可以匹配空的情況的時(shí)候妖泄，如下圖：

3.1 p = '*'

同樣將情況1融合進(jìn)來

圖4

結(jié)論：匹配成功

3.2、p為'**' 時(shí)

圖5

結(jié)論：匹配成功
也就是說艘策，當(dāng) s 為空時(shí)蹈胡，
1、如果 p 為空或者全部由星號(hào)('*')組成朋蔫，匹配成功罚渐；
2、p 除了星號(hào)('*')之外還有其他的字符或者問號(hào)('?')的時(shí)候驯妄，還是需要分析一下:

3.3荷并、 p包含星號(hào)('*')外的其他字符

3.3.1、p = '**a' 時(shí)

圖6

分析：星號(hào)('*')可以匹配空字符沒有錯(cuò)青扔，所以dp[0]源织、dp[1]都可以表示匹配成功，這個(gè)在上例中已經(jīng)分析過了微猖，可是到匹配p[2]的時(shí)候谈息，匹配失敗
結(jié)論：匹配失敗
我們?cè)僬{(diào)整一下星號(hào)('*')與'a'出現(xiàn)的先后次序

3.3.2、p = '*a*' 時(shí)

圖7

分析：同樣的凛剥，dp[0] = 1侠仇，可是dp[1] = a，依然無法匹配空字符，所以dp[1] = 0逻炊，這里的區(qū)別在于雖然p[2] = '*'互亮，可是dp[2]無法延續(xù)上述的情況，因?yàn)橹虚g被p[1]隔斷了余素，所以這里的dp[2] = 0豹休。如果從物理意義上解釋的話，p = '*a*'應(yīng)該去匹配一個(gè)字符串桨吊，字符串的格式為中間含有一個(gè)字符'a'慕爬，這個(gè)字符'a'的左右兩邊包含任意多個(gè)由空格和任意字母組成的序列，比如 s = 'cd ef a we'屏积，但是假如s 為空医窿，那肯定是匹配不上的。
結(jié)論：匹配失敗
再調(diào)換一下星號(hào)('*')與'a'出現(xiàn)的先后次序

3.3.3炊林、 p = 'a**' 時(shí)

圖8

分析：同上例一樣姥卢， p = 'a**' 是用來匹配以字符'a'開頭的，后面跟著包含任意多個(gè)由空格和任意字母組成的序列渣聚，比如 s = 'ad fwe'独榴，而s 為空的情況，也是匹配不上的奕枝。
結(jié)論：匹配失敗

3.3.4棺榔、 p 只包含星號(hào)('*')和 '?'

同樣的分析可以將上述的字符'a'換成'?'，結(jié)論也是一樣的

圖9

總結(jié)图柏，當(dāng) s 為空時(shí)序六，
1、如果 p 為空或者全部由星號(hào)('*')組成爆办，匹配成功难咕；
2课梳、p 除了星號(hào)('*')之外還有其他的字符或者問號(hào)('?')的時(shí)候距辆，匹配失敗余佃，失敗點(diǎn)在p第一次其他字母'a-z'或者問號(hào)('?')，接下來無論出現(xiàn)任何字符跨算，如果p的第一個(gè)字符不是星號(hào)('*')爆土，則從第一個(gè)位置開始均匹配失敗。

圖10

如果要將3.3節(jié)的所有情況用代碼來實(shí)現(xiàn)的話诸蚕，假設(shè) p 的長度為m時(shí)步势，定義一個(gè)數(shù)組 dp[m + 1]，用來記錄 p 與空字符串 s 匹配情況背犯，其中的dp[0] = 1坏瘩，代表 p 也為空的時(shí)候，p與s匹配成功的狀態(tài)漠魏，同時(shí)也將dp[0] = 1作為我們的初始狀態(tài)倔矾。

int m = strlen(p);
int dp[m + 1];
dp[0] = 1;
for (int i = 1; i <= m; I++)
    dp[i] = dp[i - 1] && p[i - 1] == '*';

4、s p 均不為空

有了上面的鋪墊柱锹，我們來總結(jié)最后一種情況哪自。其實(shí)，對(duì)于s禁熏、p均不為空的情況(假設(shè)s長度為n壤巷，p長度為m)，可以將以上所述的情況整合在一起瞧毙，整合的方法就是新初始化一個(gè)數(shù)組dp[m + 1][n + 1]胧华，其中的第0行和地0列的值其實(shí)就是上述所有情況的整合，而且宙彪，第0行和第0列的所有數(shù)字撑柔，可以直接算出來。我們依然從最簡(jiǎn)單的情況開始：

4.1您访、s = 'a'铅忿，p = 'b'

圖11

分析：因?yàn)閜[0] != s[0], 所以dp[1][1] = 0
結(jié)論：匹配失敗

4.2、p = 'a' 灵汪，s = 'a'

圖12

分析：因?yàn)閜[0] == s[0], 所以dp[1][1] = 1
結(jié)論：匹配成功

4.3檀训、p = '*' ，s = 'a'

圖13

分析：因?yàn)閜[0] = '*' , 可以匹配任意字符享言，所以無論s[0]為任何字母均可以匹配, 所以dp[1][1] = 1
結(jié)論：匹配成功

4.4峻凫、p = '?' ，s = 'a'

圖14

分析：因?yàn)閜[0] = '?' , 可以匹配任意非空字符览露，所以無論s[0]為任何字母均可以匹配, 所以dp[1][1] = 1
結(jié)論：匹配成功
以上四種情況荧琼，是最簡(jiǎn)單的情況，我們當(dāng)然可以通過四個(gè)if條件判斷就可以得出結(jié)果，我們接下來再升級(jí)一下難度命锄，看看能不能總結(jié)出一個(gè)規(guī)律堰乔，可以覆蓋最一般的情況。

4.5脐恩、p = 'ab' 镐侯，s = 'ab'

dp的初始化結(jié)果并結(jié)合4.2分析的dp[1][1] = 1的結(jié)論可知：

圖15

分析：本例其實(shí)就是引子的簡(jiǎn)化版，但也并沒有什么不同∈幻埃現(xiàn)在還剩下三個(gè)空格需要我們補(bǔ)充苟翻，針對(duì)本案例，我們只希望知道dp[2][2]的值骗污，因?yàn)閜[1] == s[1] == 'b' , 所以dp[2][2] = 1崇猫。
結(jié)論：匹配成功
現(xiàn)在問題來了，如果我們每次遇到p[i] == s[j], 就設(shè)定dp[i][j] = 1需忿，這個(gè)是不是我們要找的規(guī)律呢邓尤？
答案當(dāng)然是不能，請(qǐng)看下例

4.6贴谎、p = 'cb' 汞扎，s = 'ab'

dp的初始化結(jié)果并結(jié)合4.1分析的dp[1][1] = 0的結(jié)論可知：

圖16

if(p[i] == s[j]){
    if(dp[i][j] == 1)
        dp[i + 1][j + 1] = 1;
    else
        dp[i + 1][j + 1] = 0;
}

簡(jiǎn)化一下也就是這樣

if(p[i] == s[j])
    dp[i + 1][j + 1] = dp[i][j];

4.7、 p = 'a?c' 斩祭，s = 'abc'

dp的初始化結(jié)果并結(jié)合4.2分析的dp[1][1] = 0的結(jié)論可知：

圖17

if(p[i] == '?')
    dp[i + 1][j + 1] = dp[i][j];

將規(guī)律一和規(guī)律二合并之后就變成

if(p[i] == s[j] || p[i] == '?')
    dp[i + 1][j + 1] = dp[i][j];

4.8、s = 'abc'姐刁， p = 'a*c'

dp的初始化結(jié)果并結(jié)合4.2分析的dp[1][1] = 1的結(jié)論可知：

圖18

分析：dp[1][1] = 1的結(jié)論我們已經(jīng)反復(fù)看了幾遍了芥牌，下面我們來確定dp[2][2]的值，如果參考規(guī)律一和規(guī)律二的結(jié)論聂使，星號(hào)('*')可以匹配任何的字母壁拉，針對(duì)本例中dp[1][1] = 1的前提，dp[2][2]也應(yīng)該等于1柏靶，同理dp[3][3] = 1弃理，完美匹配。
結(jié)論：我們?nèi)搜劭隙ㄊ悄芸闯鍪瞧ヅ涞?br> 上面的分析屎蜓，可能會(huì)讓人誤認(rèn)為星號(hào)('*')沒有特殊的地方痘昌？錯(cuò)！
我們繼續(xù)往下看炬转。

4.9控汉、s = 'dec'， p = 'a*c'

dp的初始化結(jié)果并結(jié)合4.2分析的dp[1][1] = 0的結(jié)論可知：

圖19

分析：如果參考規(guī)律一的結(jié)論返吻，dp[1][1] = 0姑子，那么dp[2][2] 也等于0嗎？是的测僵，dp[2][2] = 0街佑，那么dp[3][3] 呢谢翎？看到p[2] == s[2] == 'c'，同樣根據(jù)規(guī)律一遞推dp[3][3] = 0沐旨，事實(shí)上dp[3][3] 也確實(shí)應(yīng)該等于 0森逮。別著急去翻4.8，再耐心往下看兩步磁携。
結(jié)論：人眼知道是匹配失敗的褒侧，但是如何讓機(jī)器代碼來計(jì)算還需要進(jìn)一步的分析

4.10、s = 'ac'谊迄， p = 'a*c'

dp的初始化結(jié)果并結(jié)合4.8分析的結(jié)論可知：

圖20

分析：我們先說結(jié)論吧闷供，s = 'ac'， p = 'a*c' 是可以匹配成功的统诺，p[0] 匹配 s[0]歪脏， p[1] 匹配空，p[2] 匹配 s[2]粮呢⌒鍪В可是當(dāng)我們用代碼來推導(dǎo)dp[3][2]的時(shí)候，是應(yīng)該依據(jù)dp[2][2]的值嗎啄寡？
結(jié)論：還是往下看吧
現(xiàn)在豪硅，是時(shí)候來總結(jié)一下星號(hào)('*')的真正規(guī)律了，在之前的所有討論中挺物，我們只關(guān)心dp數(shù)組對(duì)角的元素舟误，原因也是因?yàn)椋覀兇竽X更愿意先看到最理想或者最容易思考的情況姻乓，也就是s 和 p長度相等的情況嵌溢，其實(shí)我們也應(yīng)該關(guān)注對(duì)角線外的元素，因?yàn)轭}目的設(shè)計(jì)星號(hào)('*')的可以匹配任意字母甚至包括非空字符蹋岩，所以這就會(huì)導(dǎo)致即使p和s不等長赖草，依然可能匹配成功。

敲黑板剪个！星號(hào)規(guī)律('*')總結(jié)開始了

星號(hào)('*')的出現(xiàn)把問題的復(fù)雜度升級(jí)了許多秧骑，開始短路了。
我們?cè)賮碇厣暌幌滦翘?hào)('*')的定義：可以匹配任意字符串（包括空字符串）扣囊。
雖然星號(hào)('*')看似很強(qiáng)大乎折，但是也要考慮束縛條件，比如在例4.9中侵歇，s = 'dec'骂澄， p = 'a*c' ，p[0] != s[0]惕虑，當(dāng)要用p[1]也就是星號(hào)('*')來做匹配的時(shí)候坟冲，自然是要考慮dp[1][1]的值磨镶。再看一個(gè)星號(hào)('*')匹配空字符的情況，鞏固一下p和s不等長健提，依然可能匹配成功的例子琳猫。

4.11、s = 'abdc'私痹， p = 'a*c'

dp的初始化結(jié)果并結(jié)合4.8分析的結(jié)論可知：

圖21

圖22

圖23

圖24

圖25

圖26

if (p[i] == '*')
    dp[i + 1][j + 1] = dp[i][j + 1];

先把假設(shè)再完善一下

圖27

應(yīng)該已經(jīng)發(fā)現(xiàn)不對(duì)了芍瑞，對(duì)于左圖，在星號(hào)('*')所在的行全部置0其實(shí)沒問題褐墅，因?yàn)樽髨D本身確實(shí)匹配失敗了拆檬，可是右圖呢洪己，我們本來就知道右圖是匹配成功了呀，我們把回去看 圖4.9和4.11合并圖_b 竟贯，我們現(xiàn)在重點(diǎn)關(guān)注一下左右兩圖dp[2][2]的位置
先說相同點(diǎn)：兩個(gè)圖中dp[2][2]正上方也就是dp[1][2]的位置均為0
再說不同點(diǎn)：
左圖中答捕，dp[2][2]的左方dp[2][1]和左上方dp[1][1]均為0；
右圖中屑那，dp[2][2]的左方dp[12][1]和左上方dp[1][1]均為1拱镐。
會(huì)不會(huì)有疑問，星號(hào)('*')左方和左上方的位置一定相等呢持际？或者說當(dāng)遇到星號(hào)('*')的時(shí)候沃琅，是不是還要考慮星號(hào)('*')左方和左上方的位置的值呢？因?yàn)檫@兩個(gè)位置確實(shí)會(huì)現(xiàn)實(shí)星號(hào)('*')之前的匹配情況啊蜘欲。針對(duì)左右兩圖中的dp[2][2]益眉，其實(shí)他們左方dp[2][1]本身就是由左上方dp[1][1]值決定的，所以左方dp[2][1]已經(jīng)反應(yīng)了左上方dp[1][1]的匹配情況了姥份。
我們先把dp[2][2]的值究竟是1 還是0 先擱置下來郭脂，我們來看看dp[2][2]右側(cè)的dp[2][3]的值
先說相同點(diǎn)：兩個(gè)圖中dp[2][3]正上方也就是dp[1][3]的位置均為0，左上方也就是位置dp[1][2]均為0殿衰，dp[2][3]的左方dp[2][2]的值還不好確定
再說不同點(diǎn)：
完了朱庆，沒有不同點(diǎn)盛泡，唯一的不同點(diǎn)就是左右兩圖后面的列數(shù)不一致闷祥。
可是實(shí)際上呢，我們應(yīng)該隱隱約約可以看到傲诵，這兩個(gè)位置的值應(yīng)該也是不同的凯砍。可是這個(gè)不同怎么遞推出來呢拴竹？依然是隱隱約約可以察覺悟衩，對(duì)于位置dp[2][3]，其實(shí)左側(cè)dp[2][2]的值可以反應(yīng)出其之前的匹配情況的栓拜，同樣的座泳，dp[2][2]也是可以通過dp[2][1]來反應(yīng)區(qū)別不同。
現(xiàn)在我們先把dp[2][2]的值分別填上

圖28

dp[i][j + 1] 或者dp[i + 1][j]其中一個(gè)為1诫给，那么dp[i + 1][j + 1] 就等于 1香拉。用代碼表示如下：

if (p[i] == '*')
   dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j];

可是上面只是我們的推測(cè)啦扬，事實(shí)真的是這樣嗎？我們?cè)侔炎畛Ｒ?guī)的情況擺出來

4.12凫碌、當(dāng) p = '*a*b'扑毡，s = 'adceb' 時(shí)的初始化結(jié)果：

圖29

綜合以上的分析，全部填滿之后

圖30

4.13盛险、p = 'ab'僚楞，s = 'adceb'

dp的初始化結(jié)果并結(jié)合4.8分析的結(jié)論可知：

圖31

圖32

至此，所有的分析都結(jié)束了枉层，我們開始正式設(shè)計(jì)代碼泉褐。
1、首先要獲取p 和 s 的長度鸟蜡，假設(shè)分別為m膜赃、n；
2揉忘、聲明一個(gè)數(shù)組dp[m + 1][n + 1]跳座，并對(duì)其第零行和第零列進(jìn)行初始化；
3泣矛、分別對(duì)p 和 s進(jìn)行遍歷疲眷，將dp數(shù)組的每個(gè)位置進(jìn)行賦值
有三種情況：
3.1、 如果s[i]==p[j] or p[j]=='?' 則 dp[i+1][j+1] = dp[i][j]
3.2您朽、 如果p[j]=='*' 則dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j]
3.3狂丝、 s[i] != p[j] 則 dp[i+1][j+1]=0;
4、返回結(jié)果即dp[m][n]即可
其實(shí)，這個(gè)圖就是將圖3.6和圖2整合了一下而已。
好了启泣，到了這一步恬涧，我們就可以來分析計(jì)算剩下來的所有空格應(yīng)該對(duì)應(yīng)的值了，也就是從這一步開始，我們要分析動(dòng)態(tài)規(guī)劃里最難找的最優(yōu)子狀態(tài)了。

bool isMatch(char * s, char * p){
    int n = strlen(s);
    int m = strlen(p);
    bool dp[m + 1][n + 1];
    
    for (int i = 0; i < m + 1; i++)
        for(int j = 0; j < n + 1; j++)
            dp[i][j] = 0;
    
    dp[0][0] = true;
    for (int i = 1; i <= m; i++)
        dp[i][0] = dp[i - 1][0] && p[i - 1] == '*';
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if (s[j] == p[i] || p[i] == '?'){
                dp[i + 1][j + 1] = dp[i][j];
            }
            else if (p[i] == '*'){
                dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j];
        }
            else{
                dp[i + 1][j + 1] = 0;
            }
        }
    }
    return dp[m][n];
}