引子

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

圖1

分析：分別遍歷s和p兩個字符串，如果p[i] == s[j]，則表示匹配成功，否則直接退出循環(huán)遍歷。

用代碼也很好實現(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];

}

但是，事實并不會這樣簡單，因為有特殊符號星號('*')和問號('?')的加入，讓事情變得復(fù)雜。細致分析的話可能情況很多已經(jīng)無從下手了。

1、s 和 p 都為空

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

圖2

分析：兩個都為空，是匹配成功的。

結(jié)論：匹配成功

2、p為空

假設(shè) p = ''， s = 'abcd'，將情況1中融合進去

圖3

分析：

當(dāng) p 為空時

1、如果 s 為空的時候，匹配成功

2、如果 s 非空的時候，匹配失敗

結(jié)論：匹配失敗

3、s為空

如果拿上例來類推的話，會理所當(dāng)然的認(rèn)為：

當(dāng) s 為空時

1、如果 p 為空的時候，匹配成功

2、如果 p 非空的時候，匹配失敗

先別著急下結(jié)論，從簡到繁的分析一下吧

3.1 p = '*'

同樣將情況1融合進來

image.png

分析：星號('*')需要和前面的字符配合來使用，單獨出現(xiàn)的話無法實現(xiàn)匹配

結(jié)論：匹配失敗

3.2、p = '.'

image.png

分析：點號('.')可以匹配任意單個字符，但是空字符依然會匹配失敗

結(jié)論：匹配失敗

3.3、p = 'a'

image.png

分析：點號('.')匹配失敗，具體的字母肯定也是匹配失敗

結(jié)論：匹配失敗

可是，這不是所有可能的情況

3.4、p = '.*'

image.png

分析：雖然單獨的點號('.')會導(dǎo)致匹配失敗，但是當(dāng)點號('.')和星號('*')組合在一起，意義就變成可以匹配任何字符0-n次，正是因為可以匹配任意字符0次，所以可以匹配空字符

結(jié)論：匹配成功

3.5、p = 'a*'

image.png

分析：允許匹配0次的情況也會發(fā)生在普通的字母和星號('*')組合在一起，意義就變成可以匹配該字母0-n次，正是因為可以匹配任意字符0次，所以可以匹配空字符

結(jié)論：匹配成功

3.6、p = '.*a*'

image.png

分析：同樣，當(dāng) '.*' 和 'a*' 這樣成對并且組成序列連續(xù)出現(xiàn)的時候，依然會匹配成功

結(jié)論：匹配成功

3.7、p = '.*a'

image.png

分析：可是一旦不是完全成對出現(xiàn)的時候，比如本例，雖然 '.*' 是成對的，但是后面有一個多余的字母 'a' 就會導(dǎo)致匹配不成功

結(jié)論：匹配失敗

3.8、p = 'a.*'

image.png

分析：同樣的情況，雖然后面兩個字符 '.*' 是成對的，前面有一個多余的字母 'a' 依然會導(dǎo)致匹配不成功

結(jié)論：匹配失敗

當(dāng) s 為空時

1、如果 p 為空的時候，匹配成功

2、如果 p 非空的時候，p由連續(xù)的 '.*' 或者'a.*' 成對出現(xiàn)的時候匹配成功，否則匹配失敗

int m = strlen(p);

int dp[m + 1];

dp[0] = 1;

for (int i = 1; i <= m; ){

if(dp[i - 1] == 1 && p[i - 1] != '*' && p[i] == '*'){

dp[i] = 1;

dp[i + 1] = 1;

i += 2;

}

else{

dp[i] = 0;

i++;

}

}

4、s p 均不為空

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

4.1、p = 'b' ，s = 'a'

image.png

分析：因為p[0] != s[0], 所以dp[1][1] = 0

結(jié)論：匹配失敗

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

image.png

分析：因為p[0] == s[0], 所以dp[1][1] = 1

結(jié)論：匹配成功

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

image.png

分析：因為p[0] = '*' , 單獨的 '*' 無法匹配其他字符，所以dp[1][1] = 0

結(jié)論：匹配失敗

4.4、p = '.' ，s = 'a'

image.png

分析：因為p[0] = '.' , 可以匹配任意字符，所以無論s[0]為任何字母均可以匹配, 所以dp[1][1] = 1

結(jié)論：匹配成功

4.5、p = 'a*' ，s = 'a'

image.png

分析：因為p[0] 和 p[1]組成 'a*' 可以匹配字母'a' 0-n次 ，所以dp[1][1] = 1，dp[1][2] = 1

結(jié)論：匹配成功

4.6、p = '.*' ，s = 'a'

image.png

分析：因為p[0] 和 p[1]組成 '.*' 可以匹配任何字符甚至空字符，所以dp[1][1] = 1，dp[1][2] = 1

結(jié)論：匹配成功

4.7、p = '.*a' ，s = 'a'

image.png

分析：結(jié)合合3.4和4.5很容易理解

結(jié)論：匹配成功

4.8、p = 'a.*' ，s = 'a'

image.png

分析：同樣結(jié)合3.4和4.5的情況，與上例的區(qū)別只在于第0列的不同

結(jié)論：匹配成功

4.9、p = 'a*.*' ，s = 'a'

image.png

分析：結(jié)合例4.5和例4.6

結(jié)論：匹配成功

發(fā)現(xiàn)當(dāng) s 僅僅只有一個字母 'a' 的時候，情況已經(jīng)如此復(fù)雜，上述的九種情況也只是增加了諸如 '.*' 、'a*' 這樣能夠匹配任意字母并且成對出現(xiàn)的從而使得 p 和 s 能夠匹配成功的情況，如果將 '.*' 、'a*' 打散成不成對的情況諸如 p = '*.a*'、 '.a**'等組合，會更加讓人無法下手。所以我們需要停下來，先認(rèn)真總結(jié)一下用 p 來匹配 s 只含有一個字母的情況，然后我們再繼續(xù)往下走。

思路：動態(tài)規(guī)劃 + 遞歸

bool isMatch(char* s, char* p) {

if (*p == '\0') return *s == '\0';

if (*(p + 1) != '*') {

if (*p == *s || (*p == '.' && *s != '\0'))

return isMatch(s + 1, p + 1);

else

return false;

}

else {

while (*p == *s || (*p == '.' && *s != '\0')) {

if (isMatch(s, p + 2))

return true;

s++;

}

return isMatch(s, p + 2);

}

}

本系列文章，旨在打造LeetCode題目解題方法，幫助和引導(dǎo)同學(xué)們開闊學(xué)習(xí)算法思路，由于個人能力和精力的局限性，也會參考其他網(wǎng)站的代碼和思路，如有侵權(quán)，請聯(lián)系本人刪除。

下一題：LeetCode第11題: maxArea(C語言)

總結(jié)

以上是生活随笔為你收集整理的c语言match,LeetCode第10题: isMatch(C语言）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。