Share my straight forward DP java code. O(N^2) complexity.


  • 4
    W
    class Solution {
        public boolean isMatch(String s, String p) {
            //little trick here to avoid checking some corner cases
            return _isMatch("a" + s, "a" + p);
        }
        public boolean _isMatch(String s, String p) {
            boolean[][] valid = new boolean[p.length()][s.length()];
            valid[0][0] = true;
            for(int i = 1; i < p.length(); ++i){  	
                valid[i][0] = p.charAt(i) == '*' && valid[i-1][0];
            }
            for(int j = 1; j < s.length(); ++j){
                valid[0][j] = false;
            }
            for(int i = 1; i < p.length(); ++i){
                for(int j = 1; j < s.length(); ++j){
                    if(p.charAt(i) == '*'){
                        valid[i][j] = valid[i-1][j] || valid[i-1][j-1] || valid[i][j-1];
                    }else if( p.charAt(i) == '?'){
                        valid[i][j] = valid[i-1][j-1];
                    }else{
                        valid[i][j] = valid[i-1][j-1] && p.charAt(i) == s.charAt(j);
                    }
                }
            }
            return valid[p.length()-1][s.length()-1];
        }
    }

Log in to reply
 

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