My 16ms origin solution without knowledge of algorithm, just for beginner


  • 0
    Z

    public boolean isMatch(String s, String p) {

    if(s == null || p == null)
    	return false;
    
    //we need to find a match in s for each part
    String[] parts = p.split("\\*");
    if(parts.length == 0)
    	return true;
    
    int begin;
    
    begin = findIndex(s, parts[0], 0);
    if(begin != 0)
    	return false;
    begin = begin + parts[0].length();
    
    for(int i=1; i<parts.length; i++){
    	if(i == parts.length-1){
    		if(endwith(s, parts[i], begin))
    			return true;
    	}
    	begin = findIndex(s, parts[i], begin);
    	if(begin == -1)
    		return false;
    	begin = begin + parts[i].length();
    }
    
    if(begin < s.length() && !p.endsWith("*"))
    	return false;
    
    return true;
    

    }

    //a method like String.indexOf considering '?'

    public int findIndex(String s, String str, int begin){

    if(begin + str.length() > s.length())
    	return -1;
    
    int i = begin;
    int j = 0;
    while(i<s.length() && j<str.length()){
    	if(s.charAt(i) == str.charAt(j) || str.charAt(j) == '?'){
    		i++;
    		j++;
    	}else{
    		i = begin+1;
    		begin++;
    		j = 0;
    	}
    }
    if(j == str.length()){
    	return begin;
    }
    
    return -1;
    

    }

    //a method like String.endWith considering '?'

    public boolean endwith(String s, String str, int begin){

    int i,j;
    i = s.length()-1;
    j = str.length()-1;
    while(i >= begin && j >= 0){
    	if(str.charAt(j) == '?' || str.charAt(j) == s.charAt(i)){
    		i--;
    		j--;
    	}else{
    		return false;
    	}
    }
    if(j == -1)
    	return true;
    
    return false;
    

    }


Log in to reply
 

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