The most important is that I found using recursion is good solution to deal with the mathing.

  • 0

    ''' public static boolean handStart(char[] ch, int c_start, char[] pa, int p_start){
    char temp = 0;
    int c_index = c_start;
    int p_index = p_start;
    for( ; p_index < pa.length;){
    // at first assume that * can not appear at first element
    // we should check first element and its next // and p_index cant point to '*' character
    // check pa sequence at first
    // if the element is the last element in pa sequence
    if(p_index == pa.length-1){
    // if c_index is the last element in ch sequence and pa[p_index]='.'
    // or pa[p_index]= ch[c_index] then return true , else return false;
    if( c_index == ch.length-1 && (pa[p_index] == '.'|| pa[p_index] == ch[c_index]))
    return true;
    return false;

    		// the pa[p_index] is not the last character in pa
    		// if next pa sequence is no '*' element
    		else if( pa[p_index+1] != '*'){
    			// then we should judge if pa[p_index] and ch[c_index] matched
    			if( c_index < ch.length && (pa[p_index] == '.' || pa[p_index] == ch[c_index])){
    				temp = pa[p_index];
    				// they are not matched
    				return false;
    		// the pa[p_index] is not the last character in pa
    		// and next pa sequence is '*'
    			// where will be several situations
    			// 0. current pa character appear zero time, 
    			// 	  let next pa character of '*' to match current ch character
    			// 	  so p_index must add two
    			if( handStart(ch, c_index, pa, p_index+2))
    				return true;
    			// 1-n current pa character appear 1 to n times
    			// if current pa sequence equals to ch[c_index] 
    			//    then  current pa character appear 1 to n times
    			// use temp_c to point to next ch character
    			int temp_c = c_index;
    			// if temp_c do not IndexOfBounds 
    			while( temp_c<ch.length && ( pa[p_index] == '.' || pa[p_index] == ch[temp_c])){
    				if( handStart(ch, temp_c+1, pa, p_index+2))
    					return true;
    			//if there are not matched then return false;
    			return false;	
    	if( c_index >= ch.length)//  p_index = pa.length and c_index = ch.length
    		return true;
    	return false;//p_index <= pa.length so pa have rest of elements not matched
    public static boolean isMatch(String s, String p){
    	char[] ch = s.toCharArray();
    	char[] pa = p.toCharArray();
    	return handStart(ch, 0, pa, 0);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.