【问题】请实现一个函数用来匹配包括‘.‘和‘‘的正则表达式。模式中的字符‘.‘表示任意一个字符，而‘‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。
【思路】
首先我们先使用递归的方法，既然要写递归程序，首先考虑递归的退出条件，第一，如果str和pattern都遍历结束到了‘\0‘，返回true.第二，如果str没有遍历完，而pattern遍历结束了，则不匹配，返回false。第三，str遍历完了，但pattern没有完，可能存在‘*‘，需要进行处理，否则返回false.
假如第二个字符是‘*‘，那么分为两种情况：
如果第一个字符和pattern匹配成功（注意‘.‘的情况），那么下一步分成三个情况：
1.‘x* ‘匹配到一个字符，因此str+1, pattern+2
2.‘x* ‘匹配到多个字符，需要重复判断，因此str+1, pattern不变
3.‘x* ‘匹配到0个字符，str不动，因此，str, pattern+2
如果第一个字符和pattern不匹配，直接跳过‘x*‘, pattern+2即可！
其他情况，如果两个字符匹配，str和pattern均向后移动，str+1, pattern+1.
class Solution { public: bool match(char* str, char* pattern){ if(str == nullptr || pattern == nullptr){ return false; } return matchCore(str, pattern); } private: bool matchCore(char* str, char* pattern){ if(*str == ‘\0‘ && *pattern == ‘\0‘){ return true; } if(*str != ‘\0‘ && *pattern == ‘\0‘){ return false; } if(*(pattern+1) == ‘*‘){ // 当前字符的下一个字符是‘*‘ if(*str == *pattern || (*pattern == ‘.‘ && *str != ‘\0‘)){ return matchCore(str+1, pattern+2) || matchCore(str+1, pattern) || matchCore(str, pattern+2); }else{ return matchCore(str, pattern+2); } } if(*str == *pattern || (*pattern == ‘.‘ && *str != ‘\0‘)){ return matchCore(str+1, pattern+1); } return false; } };
原文：https://www.cnblogs.com/zhudingtop/p/11431552.html