My easy java solution using dynamic programing


  • 0
    C
    /*
    	 * Assumptions:
    	 * Assume that bother input and pattern are not null.
    	 * 
    	 * Steps: Fill out a 2D boolean array to find if there exists a matching wildcard. array[i][j] repqresents if
    	 *        there exist a wildcard matching from first element of input and pattern to ith element of input and jth element
    	 *        from pattern. 
    	 *        
    	 * Induction rules: if(p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '?'), then
    	 * 						ifMatched[j][i] = ifMatched[j][i] || ifMatched[j- 1][i - 1];
    	 * 					else if(p.charAt(i - 1) == '*'), then 
    	 * 						ifMatched[j][i] = ifMatched[j - 1][i] || ifMatched[j][i - 1];
    	 * 
    	 * return array[input.length][pattern.length].
    	 * 
    	 * Time Complexity:o(n*m)  Space Complexity:o(n*m) 
    	 */
        
        public boolean isMatch(String s, String p) {
            boolean[][] ifMatched = new boolean[1 + s.length()][1 + p.length()];
    		ifMatched[0][0] = true;
    		for(int i = 1; i <= p.length(); i++){
    			if(p.charAt(i - 1) != '*'){
    				break;
    			}
    			ifMatched[0][i] = true;
    		}
    		for(int i = 1; i <= s.length(); i++){
    			for(int j = 1; j <= p.length(); j++){
    				if(p.charAt(j - 1) == '*'){
    					ifMatched[i][j] = ifMatched[i - 1][j] || ifMatched[i][j - 1];
    				} else if(p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?'){
    					ifMatched[i][j] = ifMatched[i - 1][j - 1];
    				}
    			}
    		}
    		return ifMatched[s.length()][p.length()];
    	}
    

Log in to reply
 

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