上一题：LeetCode第9题: isPalindrome(C语言）

引子

思路：看到两个序列去匹配的问题，最自然的想法是双层循环尝试对齐匹配，我们假设表格数字为1代表匹配成功，0代表匹配失败。

图1

分析：分别遍历s和p两个字符串，如果p[i] == s[j]，则表示匹配成功，否则直接退出循环遍历。
用代码也很好实现

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];
}

但是，事实并不会这样简单，因为有特殊符号星号('*')和问号('?')的加入，让事情变得复杂。细致分析的话可能情况很多已经无从下手了。

1、s 和 p 都为空

既然无从下手，我们就用最笨的办法，从最简单的方法逐步去逼近自然的情况，自然，最简单的情况当然是 p 和 s 均为空了。

图2

分析：两个都为空，是匹配成功的。
结论：匹配成功

2、p为空

假设 p = ''， s = 'abcd'，将情况1中融合进去

图3
分析：
当 p 为空时
1、如果 s 为空的时候，匹配成功
2、如果 s 非空的时候，匹配失败
结论：匹配失败

3、s为空

如果拿上例来类推的话，会理所当然的认为：
当 s 为空时
1、如果 p 为空的时候，匹配成功
2、如果 p 非空的时候，匹配失败
先别着急下结论，从简到繁的分析一下吧

3.1 p = '*'

同样将情况1融合进来

image.png

分析：星号('*')需要和前面的字符配合来使用，单独出现的话无法实现匹配
结论：匹配失败

3.2、p = '.'

image.png

分析：点号('.')可以匹配任意单个字符，但是空字符依然会匹配失败
结论：匹配失败

3.3、p = 'a'

image.png

分析：点号('.')匹配失败，具体的字母肯定也是匹配失败
结论：匹配失败
可是，这不是所有可能的情况

3.4、p = '.*'

image.png

分析：虽然单独的点号('.')会导致匹配失败，但是当点号('.')和星号('*')组合在一起，意义就变成可以匹配任何字符0-n次，正是因为可以匹配任意字符0次，所以可以匹配空字符
结论：匹配成功

3.5、p = 'a*'

image.png

分析：允许匹配0次的情况也会发生在普通的字母和星号('*')组合在一起，意义就变成可以匹配该字母0-n次，正是因为可以匹配任意字符0次，所以可以匹配空字符
结论：匹配成功

3.6、p = '.*a*'

image.png

分析：同样，当 '.*' 和 'a*' 这样成对并且组成序列连续出现的时候，依然会匹配成功
结论：匹配成功

3.7、p = '.*a'

image.png

分析：可是一旦不是完全成对出现的时候，比如本例，虽然 '.*' 是成对的，但是后面有一个多余的字母 'a' 就会导致匹配不成功
结论：匹配失败

3.8、p = 'a.*'

image.png
分析：同样的情况，虽然后面两个字符 '.*' 是成对的，前面有一个多余的字母 'a' 依然会导致匹配不成功
结论：匹配失败
当 s 为空时
1、如果 p 为空的时候，匹配成功
2、如果 p 非空的时候，p由连续的 '.*' 或者'a.*' 成对出现的时候匹配成功，否则匹配失败

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 均不为空

有了上面的铺垫，我们来总结最后一种情况。其实，对于s、p均不为空的情况(假设s长度为n，p长度为m)，可以将以上所述的情况整合在一起，整合的方法就是新初始化一个数组dp[m + 1][n + 1]，其中的第0行和地0列的值其实就是上述所有情况的整合，而且，第0行和第0列的所有数字，可以直接算出来。我们依然从最简单的情况开始：

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

image.png

分析：因为p[0] != s[0], 所以dp[1][1] = 0
结论：匹配失败

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

image.png

分析：因为p[0] == s[0], 所以dp[1][1] = 1
结论：匹配成功

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

image.png

分析：因为p[0] = '*' , 单独的 '*' 无法匹配其他字符，所以dp[1][1] = 0
结论：匹配失败

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

image.png

分析：因为p[0] = '.' , 可以匹配任意字符，所以无论s[0]为任何字母均可以匹配, 所以dp[1][1] = 1
结论：匹配成功

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

image.png

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

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

image.png

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

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

image.png

分析：结合合3.4和4.5很容易理解
结论：匹配成功

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

image.png

分析：同样结合3.4和4.5的情况，与上例的区别只在于第0列的不同
结论：匹配成功

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

image.png

分析：结合例4.5和例4.6
结论：匹配成功
发现当 s 仅仅只有一个字母 'a' 的时候，情况已经如此复杂，上述的九种情况也只是增加了诸如 '.*' 、'a*' 这样能够匹配任意字母并且成对出现的从而使得 p 和 s 能够匹配成功的情况，如果将 '.*' 、'a*' 打散成不成对的情况诸如 p = '*.a*'、 '.a**'等组合，会更加让人无法下手。所以我们需要停下来，先认真总结一下用 p 来匹配 s 只含有一个字母的情况，然后我们再继续往下走。
思路：动态规划 + 递归

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题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。
下一题：LeetCode第11题: maxArea(C语言）