O(n) space DP, using two 1-d array to rotate.


  • 0
    Z
        public boolean isMatch(String s, String p) {
            if(p.isEmpty())
                return s.isEmpty();
                
            /*init array*/
            boolean[] d = new boolean[s.length() +1];
            boolean[] next = new boolean[s.length() +1];
            
            d[0] = true;
            for(char c: p.toCharArray()){
                next[0] = c == '*' ? d[0] : false; // init first element
                
                for(int i = 1; i <= s.length(); i ++){
                    if(c == '?'){
                        next[i] = d[i-1];
                    }
                    else if (c == '*'){
                        next[i] = d[i] || next[i-1];
                    }
                    else { // normal char
                        next[i] = d[i-1] && (c == s.charAt(i-1));
                    }
                }
                
                // rotate forward, dont have to clean up. 
                boolean[] tmp = d;
                d = next;
                next = tmp;
            }
            
            return d[s.length()];
        }

Log in to reply
 

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