剑指offer:正则表达式匹配

题目：

实现一个函数用来匹配包含' , ' 、' * ' 的正则表达式。

模式中的' . '表示任意一个字符，而' * '表示它前面的字符可以出现任意次(含0次)

在本题中，匹配指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式

"a.a" 和"ab*ac*a"匹配，但和"aa.a"和"ab*a不相配"。

思路：

可以使用递归解决。

将正则表达式的首地址指针设为 pattern ,  将待匹配字符串的首地址指针设为 str。

递归出口：1.当pattern 和 str 都指向'\0'，并且在中间匹配的过程中没有返回false, 说明中间的每一步都是匹配的。所以返回true

                    2. 当 pattern 已经指向 '\0'但是 str 没有指向 '\0'，说明不匹配，直接返回false。

                     还有一种情况是 pattern 还没有指向 '\0'，str 已经指向'\0'，这个可以返回false吗？

                     开始没有仔细思考的时候觉得可以，但是仔细思考后发现其实不行。

                     如： pattern = ".*", str = ""，这时str指向'\0'，pattern 指向 '.'，此时易得应该返回true,所以递归返回条件只有1和2.

后面还是'*'的处理情况比较复杂：

'*'的处理:    

                  1. 将'字符*' 直接忽略(因为'*'也可以匹配'字符'重复0次)。也即：match_core(str, pattern+2)

                  2. 将'字符*'当作一个'字符'。也即： match_core(str+1, pattern+2)

                  3. 将'字符*'当作多个'字符'。也就是说模式保持不变，字符指针向后匹配下一个字符，也即：match(str+1,  pattern)

细节见代码!

实现：

class Solution { public: bool match(char* str, char* pattern) { if (str == nullptr ||pattern == nullptr) return false; else return match_core(str, pattern); } bool match_core(char* str, char* pattern) { if (*str == '\0' && *pattern == '\0') return true; //递归出口，已经匹配上了 if (*pattern == '\0' && *str != '\0') return false; //不匹配, pattern已经没有了，但字符串还有 if (*(pattern+1) == '*') { if (*str == *pattern || (*pattern == '.' && *str != '\0')) { return (match_core(str+1, pattern+2) || match_core(str, pattern+2) || match_core(str + 1, pattern)); } else return match_core(str, pattern+2); //字符匹配不上，直接跳过'字符*' } //*(pattern + 1) != '*'，正常匹配即可。 if (*str == *pattern || (*pattern == '.' && *str != '\0')) return match_core(str+1, pattern+1); return false; } };