请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
1、思路：这题的解决思路主要在于如何根据' * '分情况讨论，比较字符串s和模式串p的第i位字符，分两种情况：
当*(p+1)不等于' * '时，此时只需要比较*s和*p，当*s不为空且其等于*p或*p等于' . '时，当前字符匹配，继续递归匹配s+1和p+1，条件不满足的话说明匹配失败，*s为空的时候，此时*p还不为空，匹配也失败；当*(p+1)等于' * '时，此时*p可能重复出现0次或多次，当*s不为空且其等于*p或*p等于' . '时，递归匹配s+1和p（这时候就是判断*p重复出现多次的情况），直到s和p不匹配为止，此时*s为空或者*s不等于*p，回溯的时候需要递归匹配s和p+2，这时候就是判断*p重复出现0次的情况。当字符串和模式串均为空，或者字符串不为空而模式串为空，递归终止，当模式串不为空，根据上述情况计算。
2、代码：
class Solution { public: bool match(char* s, char* p) { //字符串和模式串均为空，匹配成功 if (*s == '\0' && *p == '\0') return true; //字符串不为空，模式串为空，匹配失败 if (*p == '\0') return false; //------------模式串不为空的情况（字符串可能为空）--------------- //模式串后一位不为'*'的情况 if (*(p + 1) != '*') { if (*s != '\0' && (*s == *p || *p == '.')) { return match(s + 1, p + 1); } else { return false; } } else { bool flag = false; if (*s != '\0' && (*s == *p || *p == '.')) { flag = match(s + 1, p); } //返回值隐含了字符重复出现任意次（包括0次）的情况 return flag || match(s, p + 2); } } };3、复杂度：
时间复杂度：O( )；
空间复杂度：O( )。
1、思路：开一个二维数组f[n][m]表示字符串s的前n位与模式串p的前m位是否匹配。从后往前推，如果只关注模式串p的最后一位p[m-1]，思路就会清晰很多，分三种情况：
p[m-1]为普通字符，此时若s[n-1] = p[m-1]，说明当前字符匹配，f[n][m]的匹配情况由f[n-1][m-1]决定，即f[n][m] = f[n-1][m-1]，否则不匹配；p[m-1]为' . '，它能匹配任意字符，情况同上，f[n][m] = f[n-1][m-1]；p[m-1]为' * '，此时说明p[m-2]可能重复0次或多次，当s[n-1] != p[m-2]，必然重复0次，当s[n-1] = p[m-2]或者p[m-2] = ' . '，可能重复0次或多次，因此重复0次的情况可以先合并，重复0次就是跳过这两个字符，f[n][m]的匹配情况由f[n][m-2]决定，即f[n][m] = f[n][m-2]；剩下的就是s[n-1] = p[m-2]或者p[m-2] = ' . '时p[m-2]重复多次的情况，此时f[n][m] = f[n-1][m]，因为可能重复1次或多次，此时字符串s往前挪一位，模式串不变，继续看s[n-2]与p[m-2]是否匹配。初始条件：f[0][0] = 1，即空串空正则匹配，f[1...n][0] = 0，即非空串空正则不匹配，然后就可以自底向上计算。
2、代码：
class Solution { public: bool match(char* s, char* p) { int ns = strlen(s), np = strlen(p); vector<vector<int> > res(ns + 1, vector<int>(np + 1, 0)); for (int i = 0; i <= ns; i++) { for (int j = 0; j <= np; j++) { if (j == 0) { res[i][j] = (i==0) ? 1 : 0; } else { if (p[j - 1] != '*') { if (i >= 1 && (s[i - 1] == p[j - 1] || p[j - 1] == '.')) { res[i][j] = res[i - 1][j - 1]; } } else { if (j >= 2) { res[i][j] += res[i][j - 2]; } if (i >= 1 && j >= 2 && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) { res[i][j] += res[i - 1][j]; } } } } } return res[ns][np]; } };3、复杂度：
时间复杂度：O(nm)；
空间复杂度：O(nm)。
