Regular Expression Matching

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Hint: the most tricky part is how to handle the string with '*'. When there is no '*', it is easy, we just match the character at current location of string p to the current character of s. If they have the same character, or the character at p is '.', we proceed to the next position and call the function recursively. Otherwise we return false.

Here comes the '*'. This character means that it can match 0 or more of the characters prior to it. So that a* can be interpreted as "", "a" "aa", "aaa". Therefore, when we meet a '*', it is possible that it can match its previous 0, 1, ...n characters. If so, we try these possible matchings one by one recursively in or iteration, and the new sequence of p will start right after '*', if we found a match, we just return true. After the iteration, the positions moved to the end of the string, and we check the match again, as shown in line 19-25.

01 public boolean isMatch(String s, String p) {

02     char [] str1=s.toCharArray();

03     char [] str2=p.toCharArray();

04     return isMatch(str1,str2,0,0);        

05 }

06 

07 public boolean isMatch(char [] str1, char [] str2, int start1, int start2)

08 {

09     if(start2==str2.length)

10         return start1==str1.length;

11   

12    //next character is not '*'

13     if(!(start2<str2.length-1 && str2[start2+1]=='*' ))

14     {

15         return (start1<str1.length) && (str1[start1]==str2[start2] ||str2[start2]=='.') && isMatch(str1,str2,start1+1,start2+1);  

16     }

17   

18    //next character is '*'

19     while(start1<str1.length && start2<str2.length && (str1[start1]==str2[start2] || str2[start2]=='.'))

20     {

21         if(isMatch(str1,str2,start1,start2+2))

22             return true;

23         start1++;

24     }        

25     return isMatch(str1,str2,start1,start2+2);

26 }