正则表达式匹配(.和*)

剑指offer和leetcode10
请实现一个函数用来匹配包括‘.’和*表达式。模式中的字符‘.’表示任意一个字符，而*表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配
e.g.
match(“aa”,”a”) → false
match(“aa”,”aa”) → true
match(“aaa”,”aa”) → false
match(“aa”, “a*”) → true
match(“aa”, “.*”) → true
match(“ab”, “.*”) → true
match(“aab”, “c*a*b”) → true

分析：设当前要匹配的字符串为str, 当前位置为start1, str长度为len1,
模式串为pattern, 模式串当前位置为start2, str长度为len2

1.  如果start1==len1&&start2==len2, 则匹配，return true：
2.  如果start2==len2&&start1!=len1, 不匹配，return false
3.  如果start1的后一个位置为\*时：
       如果str[start1]==pattern[start2]或 pattern[start2]==‘.’时，那么有2中可能，  一种是字符串当前位置后移一位，模式串当前位置不变，即匹配字符串后一位，  或模式串后移2位，相当于\* 及其前面的字符自动忽略。
       若str[start1]！=pattern[start2]且pattern[start2]!=‘.’, 那模式串与字符串不匹配，模式串后移2位。
4.   如果str[start1]==pattern[start2]或 pattern[start2]==‘.’时，字符串和模式串当前位置都后移1为
5.   其他情况， 不可能匹配，return false;

bool ismatch(char* str,int start1,int len1,char* pattern,int start2,int len2)
{
if(start1==len1&&start2==len2)
return true;
if(start2==len2)
return false;
if(start2+2<=len2&&pattern[start2+1]=='*')
    {
if(pattern[start2]=='.'||pattern[start2]==str[start1])
        {
if(start1+1<=len1)
return ismatch(str,start1+1,len1,pattern,start2,len2)||ismatch(str,start1,len1,pattern,start2+2,len2);
else
return ismatch(str,start1,len1,pattern,start2+2,len2);
        }
else
return ismatch(str,start1,len1,pattern,start2+2,len2);
    }
if(pattern[start2]=='.'||pattern[start2]==str[start1])
return ismatch(str,start1+1,len1,pattern,start2+1,len2);
return false;
}
bool match(char* str, char* pattern)
{
int i,j,len1=strlen(str),len2=strlen(pattern);
if(len1==0&&len2==0)
return true;
if(len2==0)
return false;
return ismatch(str,0,len1,pattern,0,len2);
}