44. Wildcard Matching

Posted on | Edited on | Views:

LeetCode

Approach 1: Brute Force -> Recursion, Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public boolean isMatch(String s, String p) {
        int sLen=s.length(),pLen=p.length();
        if(sLen==0&&pLen==0) return true;
        if(sLen>0&&pLen==0) return false;
        // corner cases like: s: "", p: "****"
        if(sLen==0&&pLen>0){
            if(p.charAt(0)=='*'&&isMatch(s,pLen>1?p.substring(1):"")) return true;
            else return false;
        }
        
        // if two characters are same, index++
        if(s.charAt(0)==p.charAt(0)||p.charAt(0)=='?'){
            if(isMatch(sLen>1?s.substring(1):"",pLen>1?p.substring(1):"")) return true;
        } 

        // case: s>0,p>0
        if(p.charAt(0)=='*'){
            if(isMatch(s,pLen>1?p.substring(1):"")||isMatch(sLen>1?s.substring(1):"",p)) return true;
        }
        return false;
    }
}
/*
class Solution {
    public boolean isMatch(String s, String p) {
        int sLen=s.length(),pLen=p.length();
        if(sLen==0&&pLen==0) return true;
        if(sLen>0&&pLen==0) return false;

        // corner cases like: s: "", p: "****"
        if(sLen==0&&pLen>0){
            if(p.charAt(0)=='*'&&isMatch(s,pLen>1?p.substring(1):"")) return true;
            else return false;
        }
        
        // if two characters are same, index++
        if(s.charAt(0)==p.charAt(0)||p.charAt(0)=='?'){
            return isMatch(sLen>1?s.substring(1):"",pLen>1?p.substring(1):"");
        } 

        // case: s>0,p>0
        if(p.charAt(0)=='*'){
            if(pLen==1) return true;
            else{
                for(int i=0;i<sLen;i++){
                    if(isMatch(s.substring(i),p.substring(1))) return true;
                }
            }
        }
        return false;
    }
}*/

Bottom up DP, Time complexity: O(SP) link
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isMatch(String s, String p) {
        int sLen=s.length(),pLen=p.length();
        boolean[][] dp=new boolean[sLen+1][pLen+1];
        // base case, if both s and p are empty then match is true;
        dp[0][0]=true;
        // if p is empty and s is not empty then no match exists;
        for(int i=1;i<=sLen;i++) dp[i][0]=false;
        // if s is empty then the match exits only when p is like "*******";
        for(int i=1;i<=pLen;i++) dp[0][i]=dp[0][i-1]&&p.charAt(i-1)=='*';
        // when s and p are not empty at the same time;
        for(int i=1;i<=sLen;i++){
            for(int j=1;j<=pLen;j++){
                if(p.charAt(j-1)=='?'||s.charAt(i-1)==p.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else if(p.charAt(j-1)=='*'){
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                }
            }
        }
        return dp[sLen][pLen];
    }
}

Top Down DP -> Recursion + Memoization link

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private boolean isMatchUtil(String s, String p, int start_s, int start_p){
        if(start_s==s.length()&&start_p==p.length()) return true;
        else if(start_s!=s.length()&&start_p==p.length()) return false;
        else if(start_s==s.length()&&start_p!=p.length()){
            return p.charAt(start_p)=='*'&&isMatchUtil(s,p,start_s,start_p+1);
        }
        else if(p.charAt(start_p)=='*') 
            return isMatchUtil(s,p,start_s+1,start_p)||isMatchUtil(s,p,start_s,start_p+1);
        else if(p.charAt(start_p)=='?'||s.charAt(start_s)==p.charAt(start_p)) 
            return isMatchUtil(s,p,start_s+1,start_p+1);
        return false;
    }
    public boolean isMatch(String s, String p) {
        return isMatchUtil(s,p,0,0);
    }
}

DP: recursion + memoization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private boolean isMatchUtil(String s, String p, int start_s, int start_p, Boolean[][] memo){
        if(memo[start_s][start_p]!=null) // If the computation is already done, directly return the cached result
            return memo[start_s][start_p];
        boolean tmp=false;
        
        if(start_s==s.length()&&start_p==p.length()) tmp=true;
        else if(start_s!=s.length()&&start_p==p.length()) tmp=false;
        else if(start_s==s.length()&&start_p!=p.length()){
            tmp=p.charAt(start_p)=='*'&&isMatchUtil(s,p,start_s,start_p+1,memo);
        }
        else if(p.charAt(start_p)=='*') 
            tmp=isMatchUtil(s,p,start_s+1,start_p,memo)||isMatchUtil(s,p,start_s,start_p+1,memo);
        else if(p.charAt(start_p)=='?'||s.charAt(start_s)==p.charAt(start_p)) 
            tmp=isMatchUtil(s,p,start_s+1,start_p+1,memo);
        memo[start_s][start_p]=tmp; //Before returning the result, cache it !
        return tmp;
    }
    public boolean isMatch(String s, String p) {
        Boolean[][] memo=new Boolean[s.length()+1][p.length()+1]; //Define the cache
        return isMatchUtil(s,p,0,0,memo);
    }
}

0%