hello，大家好，本文为大家讲解leetcode算法第10题，正则表达式匹配。
题目
给定一个字符串str以及一个模式串pattern，实现一个支持"*"和"."的正则表达式匹配，其中"*"匹配零个或任意个前一字符，"."匹配任意单个字符，若pattern能完整匹配str，则输出true，否则输出false。例子如下：
| str | pattern | 输出 |
| aaa | .* | true |
| aaa | .*b*c*d* | true |
| cab | d*c.b* | true |
解法1
此题很容易写出算法伪代码：
if (str[sIdx] == pattern[pIdx] || pattern[pIdx] == '.') {// 当前字符匹配成功} else {// 当前字符匹配失败}
所以本题只需要把上述两种情况厘清，问题也变迎刃而解了。
匹配失败
当前字符匹配失败，若pattern下一字符为'*'，则继续匹配str[sIdx: ]与pattern[pIdx + 2: ]，否则直接返回false即可。注意此处便出现了第一个递归点，我们此填充到代码：
bool backtrack(char *str, char *pattern, int sIdx, int pIdx){// 递归出口if (str[sIdx] == pattern[pIdx] || pattern[pIdx] == '.') {// 当前字符匹配成功} else {// 当前字符匹配失败if (pattern[pIdx + 1] == '*') {return backtrack(str, pattern, sIdx, pIdx + 2);} else {return false;}}}
匹配成功
当前字符匹配成功时，情况稍微复杂一点点，观察下述几种情况：
case1
首先是最为简单的情况，如str="abc"，pattern="acb"，当前字符匹配，直接进行str[sIdx+1: ]与pattern[pIdx+1: ]匹配即可。
case2
形如str="bbb"，pattern="b*"，此时继续匹配str[sIdx+1:]与pattern[pIdx: ]即可。
case3
形如str="bbbcd"，pattern="b*bcd"，此种情况与case2不同的是，‘*’并不能匹配到不能匹配位置，否则会导致后续匹配失败，此时应该继续匹配str[sIdx+1: ]与pattern[pIdx+2: ]。
case4
形如str="abd"，pattern="a*abd"，此处应该继续匹配str[sIdx: ]与pattern[pIdx+2: ]。
递归出口
若str到达结尾且pattern也达到结尾，显然匹配成功，但也有str="v"，pattern="vb*d*n*"的情况，需要单独判断，此外的情况则匹配失败。
至此，整理上述思路便得到递归函数的代码：
bool backtrack(char *str, char *pattern, int sIdx, int pIdx){// 递归出口if (sIdx == strLen) {return pIdx == patternLen ||(pIdx + 1 < patternLen && pattern[pIdx + 1] == '*' && backtrack(str, pattern, sIdx, pIdx + 2));} else {return false;}if (str[sIdx] == pattern[pIdx] || pattern[pIdx] == '.') {// 当前字符匹配成功if (pattern + 1 < patternLen && pattern[pIdx + 1] == '*") {return backtrack(str, pattern, sIdx + 1, pIdx) ||backtrack(str, pattern, sIdx + 1, pIdx + 2) ||backtrack(str, pattern, sIdx, pIdx + 2);} else {return backtrack(str, pattern, sIdx + 1, pIdx + 1);}} else {当前字符匹配失败if (pattern[pIdx + 1] == '*') {return backtrack(str, pattern, sIdx, pIdx + 2);} else {return false;}}}
优化
显然上述递归过程中，存在大量重复搜索的情况，这会大大增加时间复杂度，因此可以定义记忆数组，进行记忆化搜索。
整个算法题的代码如下：
int sLen, pLen;bool backtrack(char *s, char *p, int sIdx, int pIdx, int **memo){// 记忆化剪枝if (memo[sIdx][pIdx] == false) {return false;}// 递归出口if (sIdx == sLen) {memo[sIdx][pIdx] = (pIdx == pLen) ||((pIdx + 1 < pLen) && p[pIdx + 1] == '*' && backtrack(s, p, sIdx, pIdx + 2, memo));return memo[sIdx][pIdx];} else if(pIdx == pLen) {memo[sIdx][pIdx] = 0;return false;}if (s[sIdx] == p[pIdx] || p[pIdx] == '.') { // 匹配成功if (pIdx + 1 < pLen && p[pIdx + 1] == '*') {memo[sIdx][pIdx] = backtrack(s, p, sIdx + 1, pIdx, memo) ||backtrack(s, p, sIdx + 1, pIdx + 2, memo) ||backtrack(s, p, sIdx, pIdx + 2, memo);return memo[sIdx][pIdx];} else {memo[sIdx][pIdx] = backtrack(s, p, sIdx + 1, pIdx + 1, memo);return memo[sIdx][pIdx];}} else { // 匹配失败if (pIdx + 1 < pLen && p[pIdx + 1] == '*') {memo[sIdx][pIdx] = backtrack(s, p, sIdx, pIdx + 2, memo);return memo[sIdx][pIdx];} else {memo[sIdx][pIdx] = 0;return false;}}}bool isMatch(char * s, char * p){sLen = strlen(s);pLen = strlen(p);int **memo = (int **)malloc(sizeof(int *) * (sLen + 1));for (int i = 0; i <= sLen; ++i) {memo[i] = (int *)malloc(sizeof(int) * (pLen + 1));}for (int i = 0; i <= sLen; ++i) {for (int j = 0; j <= pLen; ++j) {memo[i][j] = 1;}}return backtrack(s, p, 0, 0, memo);}
解法2
解法1需要对各种情况有一个精确判断，特别是匹配成功且模式串下一字符为'*'时，很容易遗漏某一种情况而造成解法不够完整。
若我们只关心当前匹配字符与下一个匹配字符的情况，则有以下几种情形：
p为空，当且仅当s为空时匹配
s不为空，则*s == *p 或者 *p=='.'时继续匹配
*(p+1) != ' '，则双指针后移继续匹配
*(p+1)=='*'，分两种情况：①'*'匹配0个字符，s匹配剩下的；②'*'匹配一个字符，然后用p继续匹配s
翻译为代码：
bool isMatch(char *s, char *p){if (!(*p)) {return !(*s);}bool firstMatchIdx = (*s) && (*s == *p || *p == '.');if (*(p + 1) == '*') {return isMatch(s, p + 2) || (firstMatchIdx && isMatch(s + 1, p));} else {return firstMatchIdx && isMatch(s + 1, p + 1);}}
后记
正则表达式在字符串搜索与替换中，是强有力的生产力工具，本文只是以题目为切入点，窥探了正则表达式冰山一角，后续还会带来一篇较为详细的文章进行介绍。欢迎读者勘误或提出有效建议（seuhyz@163.com）。
