描述：

实现.和*号匹配，*表示前面字符0~无穷个，.表示任意一个字符。

要求全部，匹配，不是部分匹配。

 

解决：

思路类似最长公共子序列，

dp[i][j] = dp[i - 1][j - 1], 如果s[i] == p[j] || p[j] == '.'

              dp[i][j - 2], 如果p[j] == '*' && s[i] != p[j - 1]

              dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j - 2] || dp[i][j - 2], 如果p[j] == '*' && s[i] == p[j - 1]

稍稍解释下：

对于s和p，设各个最后一个字符为x, y，p的倒数第二字符为z，除此外前面字符设为S,P，则：

s = Sx

p = Pzy

如果x == y或y == '.'，则如果S和Pz匹配，则s和p匹配，因为最后两字字母是匹配的。这就缩减了问题规模。

而对于y ==  '*'的情况，需要考虑z：

    如果x != z，则只有在s和P匹配的情况下，s和p才匹配。

    如果x == z，设匹配符号为~吧，方便，则如果S~P，S~Pz，S~Pzy，Sx~P，Sx~Pz，都可得出s和p匹配。

 

代码压缩了空间，用一些额外变量保存会用到的变量。时间复杂度O(m*n)，空间复杂度O(n)。

bool cmatch(char s, char p) {    return p == '*' || p == '.' || s == p;}bool isMatch(string s, string p) {    int m = s.size();    int n = p.size();    bool* arr = new bool[n + 1]();    arr[0] = 1;    for (int i = 2; i <= n; ++i)        if (p[i - 1] == '*' && arr[i - 2] == true) arr[i] = true;    int j2 = arr[0];    int j1 = arr[1];    int sa = arr[2];    for (int i = 1; i <= m; ++i) {        for (int j = 0; j <= n; ++j)            if (j == 0) {                j2 = arr[0];                arr[0] = false;            }            else if (j == 1) {                j1 = arr[1];                arr[1] = i == 1 && cmatch(s[0], p[0]);            }            else {                sa = arr[j];                if (p[j - 1] == '*')                    arr[j] = cmatch(s[i - 1], p[j - 2]) && (arr[j] || arr[j - 1] || j1 || j2 || arr[j - 2])?true:arr[j - 2];                else                    arr[j] = cmatch(s[i - 1], p[j - 1])?j1:false;                j2 = j1;                j1 = sa;            }    }    return arr[n];}