引子

思路：看到兩個(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 的長(zhǎng)度為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長(zhǎng)度為n，p長(zhǎng)度為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)化版，但也并沒有什么不同?，F(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)?，我們大腦更愿意先看到最理想或者最容易思考的情況，也就是s 和 p長(zhǎng)度相等的情況，其實(shí)我們也應(yīng)該關(guān)注對(duì)角線外的元素，因?yàn)轭}目的設(shè)計(jì)星號(hào)('*')的可以匹配任意字母甚至包括非空字符，所以這就會(huì)導(dǎo)致即使p和s不等長(zhǎng)，依然可能匹配成功。

敲黑板！星號(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不等長(zhǎng)，依然可能匹配成功的例子。

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 的長(zhǎng)度，假設(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];
}