【剑指offer】正则表达式匹配

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

题解：我们开始匹配第一个字符的时候，可能不是相同的。

但是后面可能会出现'*'，导致它匹配成功，所以我们要分情况讨论它的下一个字符。

1、不为'*'。那么我们直接匹配当前的字符。成功：相同字符或者出现’.‘，就去匹配下一个；失败返回false。

2、为‘*’。这时候又要分两种情况。

‘*’没有匹配到字符，str不变，pattern字符后移两位，跳过'*'去判断。
‘*’匹配到字符时，pattern不做改变，因为我们可以匹配到很多字符。所以移动str的下一个去做判断。

记得判断两种特殊情况。

代码：

 1 class Solution {
 2 public:
 3     bool match(char* str, char* pattern)
 4     {
 5         if(*str == '' && *pattern == '')    return true;
 6         if(*str != '' && *pattern == '')    return false;
 7         
 8         if(*(pattern+1) != '*' ){
 9             if(*str == *pattern || (*str !='' && *pattern == '.'))
10                 return match(str+1,pattern+1);
11             else    return false;
12         }
13         else{
14             if(*str == *pattern || (*str !='' && *pattern == '.'))
15                 return match(str,pattern+2) || match(str+1,pattern);
16             else
17                 return match(str,pattern+2);
18         }
19     }
20 };