Java DP solution


  • 1
    D
    public static boolean isMatch(String s, String p) {
    		if(s.isEmpty() && p.isEmpty())
    			return true;
    
    		if(p == null || p.isEmpty())
    			return false;
    
    		//s = "" && p="ab*" -- false;
    		//"" && "a" -- false
    		//"" and "*a*" -- false
    		if(s.isEmpty()){
    			if(!p.contains("*")){
    				return false;
    			}
    			else{
    				StringBuilder sb = new StringBuilder();
    				for(int i=0; i<p.length(); i++){
    					if(p.charAt(i) != '*')
    						sb.append(p.charAt(i));
    				}
    				if(sb.toString().length() == 0){
    					return true;
    				}
    				return false;
    			}
    		}
    
    		boolean [][] dp = new boolean[p.length()+1][s.length()+1];
    		dp[0][0] = true;
    
    		for(int q=1; q<dp.length; q++){
    			dp[q][0] = p.charAt(q-1) == '*'? dp[q-1][0]: false;
    		}
    
    		for(int k=1; k<dp[0].length; k++){
    			dp[0][k] = false;
    		}
    
    		for(int i=1; i<dp.length; i++){
    			for(int j=1;j<dp[0].length; j++){
    
    				if((p.charAt(i-1) == s.charAt(j-1) || (p.charAt(i-1) == '?'))
    						&& dp[i-1][j-1]){
    					dp[i][j] = true;
    				}
    				//as long as one of those three values is true, dp[i][j] is true
    				else if(p.charAt(i-1) == '*'){
    					dp[i][j] = dp[i-1][j] || dp[i-1][j-1] || dp[i][j-1];
    				}
    			}
    		}
    
    		return dp[p.length()][s.length()];
    	}

Log in to reply
 

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