前言

正则表达式匹配也是编程中很常见的技术，那么给定正则表达式匹配的规则，那么对于模式串，如何判断字符串是否与之匹配呢？这就涉及到了字符串的编程能力。字符串的应用也是面试中非常重要的一类。

题目(正则表达式匹配)

题目：请实现一个函数用来匹配包括 ‘.’ 和 ‘*‘ 的正则表达式。模式中的字符 ‘.’ 表示任意一个字符，而 ‘‘ 表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 “aaa” 与模式 “a.a” 和 “ab\ac*a” 匹配，但是与 “aa.a” 和 “ab*a” 均不匹配。

算法思路

很明显需要利用递归。
首先考虑下递归的出口。如果字符串与模式串能够匹配，那么此时，他们都匹配到了字符终止标记’\0’；否则，如果字符串还未到达’\0’,而模式串已经到达了 ‘\0’,那么说明此时匹配不成功。

接下来我们先考虑含 * 的情况，这里要注意含 * 的情况有包含一些 . 的情况，所以我们需要先考虑 * 的情况。
那么如果模式串的下一个字符是 * ，首先分为两种情况。
情况一：如果字符串和模式串的第一个字符相等或者模式串中第一个字符含 ‘.’而字符串未到达末位，那么又可以分为三种子情况：

如果字符串的第一个字符和模式串的第一个字符不相等，字符串可以继续和模式串中的下下一个字符判断匹配(忽略 * 本身及其前面的字符)；
如果字符串的第一个字符和模式串的第一个字符相等，那么字符串继续前进，然后可以和模式串的第一个字符开始匹配。
如果字符串的第一个字符和模式串的第一个字符相等，那么字符串继续前进，然后可以和模式串中 ‘*‘ 的下一个字符开始匹配(忽略 * 本身及其前面的字符)。

情况二：字符串第一个字符和模式串第一个字符都匹配，或者模式串中含 . 并且字符串第一个字符不是’\0’，那么字符串和模式串继续前进一位匹配。

算法实现

复杂度分析

算法需要对每个字符都进行匹配，因此时间复杂度为 O(n)，另外由于采用递归，需要消耗 O(n)的递归工作栈，所以空间复杂度为 O(n)。

参考

<<剑指offer2>>