[leetcode]Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' 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

代码：

 

 
//递归从左至右依次匹配
public boolean isMatch(String s, String p) {
	        // Note: The Solution object is instantiated only once and is reused by each test case.
	        if(s == null||p == null) return false;
	        return isMatch(s,p,0,0);
	    }
	    //递归函数isMatch(s,p,i,j)：i 指示 s , j 指示p
	    public boolean isMatch(String s,String p,int i, int j){
	        int slen = s.length();
	        int plen = p.length();
	        
	        
	        if(j>=plen){//递归结束
	            if(i>=slen) return true;
	            else return false;
	        }
	        if(j == plen-1){//j已经指向最后一位，递归结束
	            if(i!=slen-1) return false;
	            if(s.charAt(i) == p.charAt(j)||p.charAt(j) == '.') return true;
	            return false;
	        }
	        
	        char c = p.charAt(j+1);
	        if(c != '*'){//p[j+1] !=‘ * ‘ 说明当前p[j]只能匹配一个
	             if(i<=slen-1&&(s.charAt(i) == p.charAt(j)||p.charAt(j) =='.'))
                          return isMatch(s,p,i+1,j+1);//继续匹配后续字符串 
                     else
	                  return false;
	        }else{
                 //匹配0（注意可以是0个，所以i没有++）到多个p[j]或者任意字符（p[j] =='.' ）
 	            while(i<=slen-1&&(s.charAt(i) == p.charAt(j)||p.charAt(j) =='.')){
	                if(isMatch(s,p,i,j+2)) return true;
	                i++;
	            }
	            return isMatch(s,p,i,j+2);//走到第一个不匹配的之后，继续后续过程
	        }
	    }