Accepted Java DP solution. O(s.length*p.length) time and space complexity;


  • 0
    O
        public boolean isMatch(String s, String p) { 
        	int i, j; 
        	int sLen = s.length();
        	int pLen = p.length();
        	boolean[][] states = new boolean[sLen+1][pLen+1];
        	for(i = 0; i <= sLen; i++) Arrays.fill(states[i], false);
        	//Empty string match empty pattern
        	states[0][0] = true;
        	//'*' character can match empty string
        	for(i = 1; i <= pLen; i++) {
        		if (p.charAt(i-1) == '*') {
        			states[0][i] = states[0][i-1];
        		}
        	}
        	char sCh, pCh;
        	for(i = 1; i <= sLen; i++) {
        		sCh = s.charAt(i-1);
        		for(j = 1; j <= pLen; j++){
        			pCh = p.charAt(j-1);
        			//'?' matches any single character 
        			if (pCh == '?' || pCh == sCh) {
        				states[i][j] = states[i-1][j-1];
        			}
        			//'*' matches any sequence of characters (including the empty sequence)
        			else if (pCh == '*') {
        				states[i][j] = states[i][j-1] || states[i-1][j];
        			}
        			//characters do not match
        			else {
        				states[i][j] = false;
        			}
        		}
        	}
        	
            return states[sLen][pLen];
        }
    

Log in to reply
 

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