Suggestions for non-recursive solution s for regular expression matching


  • 0
    Y
    /** Method 2: non-recursive */
    public static boolean isMatch(String s, String p) {    
    if(s.length() == 0 && p.length() == 0)  return true;
    	if(p.length() == 0)  return false;
        
    	int i = 0, j = 0, spos = 0, pos = -1;
    	while(i < s.length()){  
    	    if(j == p.length()-1) {
    			if(p.charAt(j) =='.' || p.charAt(j) == s.charAt(i) || p.charAt(j) == '*') {
    				i++;
    				j++;
    				continue;
    			}
    		}
    		if(j < p.length()-1 && p.charAt(j+1) != '*') {
    			if(p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {
    				i++;
    				j++;  	
    				continue;
    			}  			
    		}   			
    		if(j < p.length()-1 && p.charAt(j+1) == '*' ) {
    			pos = j;
    			spos = i;  			
    			
    			if(j+2 < p.length() && p.charAt(j+2) == s.charAt(i)) {  //x* occurrence is 0	  				
      				j = j+3;
      				i = i+1;  	  				
      		 	  				
      				if(j < p.length()) 	continue;  	  				
      				if(j == p.length() && i == s.length()) 
      					return true;  						
      				else
      					return false;  	 	  			
      			}	
    			
    			if(p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {  //x* occurrence is more than 1
    				j = j+2;
    				i = i+1;
    				continue;
    			}   				
    		}	
    
    		if(pos != -1) { 
    		    i = ++ spos;
    			j = pos+2;   					
    			continue;
    		}  
    		
    		return false;  			
    	}
    
    	while(j < p.length()-1 && p.charAt(j+1) == '*') //eg., p="c*c*"
    		j = j+2;
    	
    	return j == p.length() ? true: false;
    }
    

    Above code can pass 388 test cases. But for the normal char*, i do not make it very good. I would like to get help from here. I wish people here can correct my mistakes. I am just a beginner of the algorithms. Thanks.


  • 0
    W
    This post is deleted!

  • 0
    S

    Could you please re-post your answer with explanation of algorithm and comment in code? Thanks.


  • 0
    R

    It doesn't matter if you can do it right in C++ style string. If you want to use C style string like char *p, you need to implement some of the functions of C++ style string like s.length() (you may use strlen(char *p) instead). In addition, a c style string contains an end flag '\0' to indicate the end of a string while C++ style string doesn't.


Log in to reply
 

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