10. Regular Expression Matching

Posted on | Edited on | Views:

LeetCode

Recursive (link)

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
54
55
56
57
58
59
class Solution {
    private boolean isMatch(String s,int i,String p,int j){
        int sLen=s.length(),pLen=p.length();
        if(j==pLen) return i==sLen;
        
        boolean firstMatch=(i<sLen) && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.');
        if(j+1<pLen && p.charAt(j+1)=='*'){
            if(isMatch(s,i,p,j+2) || firstMatch && isMatch(s,i+1,p,j)) return true;
        }else{
           if(firstMatch && isMatch(s,i+1,p,j+1)) return true; 
        }
        return false;
    }
    
    public boolean isMatch(String s, String p) {
        return isMatch(s,0,p,0);
    }
}

/* comments for easier understanding
class Solution {
    private boolean isMatch(String s,int i,String p,int j){
        int sLen=s.length(),pLen=p.length();
        // if (pattern.isEmpty()) return text.isEmpty();
        if(j==pLen) return i==sLen;
        
        boolean firstMatch=(i<sLen) && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.');
        if(j+1<pLen && p.charAt(j+1)=='*'){
            // ignore this part of the pattern,
            if(isMatch(s,i,p,j+2)) return true; 
            // delete a matching character in the text
            if(firstMatch && isMatch(s,i+1,p,j)) return true;
        }else{
            // if initial inputs match, the remaining strings after any of these operations should match
           if(firstMatch && isMatch(s,i+1,p,j+1)) return true; 
        }
        return false;
    }
    
    public boolean isMatch(String s, String p) {
        return isMatch(s,0,p,0);
    }
}*/

/*
class Solution {
    public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();
        boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

        if (pattern.length() >= 2 && pattern.charAt(1) == '*') { // delete a matching character in the text
            return (isMatch(text, pattern.substring(2)) // ignore this part of the pattern,
            || (first_match && isMatch(text.substring(1), pattern))); //delete a matching character in the text
        } else {
            //  If we have a match on the initial inputs, the remaining strings after any of these operations matched
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }
}*/

DP: Top Down

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
class Solution {
    private boolean isMatch(String s,int i,String p,int j,Boolean[][] dp){
        if(dp[i][j]!=null) return dp[i][j];
        int sLen=s.length(),pLen=p.length();
        if(j==pLen) return dp[i][j]=(i==sLen)?true:false;
        
        boolean tmp=false;
        boolean firstMatch=(i<sLen) && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.');
        if(j+1<pLen && p.charAt(j+1)=='*'){
            if(isMatch(s,i,p,j+2,dp) || firstMatch && isMatch(s,i+1,p,j,dp)) tmp=true;
        }else{
           if(firstMatch && isMatch(s,i+1,p,j+1,dp)) tmp=true; 
        }
        return dp[i][j]=tmp;
    }
    
    public boolean isMatch(String s, String p) {
        Boolean[][] dp=new Boolean[s.length()+1][p.length()+1];
        return isMatch(s,0,p,0,dp);
    }
}
/*
enum Val{TRUE,FALSE,UNKNOWN}

class Solution {
    private Val isMatch(String s,int i,String p,int j,Val[][] dp){
        if(dp[i][j]!=Val.UNKNOWN) return dp[i][j];
        int sLen=s.length(),pLen=p.length();
        if(j==pLen) return dp[i][j]=(i==sLen)?Val.TRUE:Val.FALSE; 
        
        boolean firstMatch=(i<sLen) && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.');
        if(j+1<pLen && p.charAt(j+1)=='*'){
            if(isMatch(s,i,p,j+2,dp)==Val.TRUE) return dp[i][j]=Val.TRUE;
            if(firstMatch && isMatch(s,i+1,p,j,dp)==Val.TRUE) return dp[i][j]=Val.TRUE;
        }else{
           if(firstMatch && isMatch(s,i+1,p,j+1,dp)==Val.TRUE) return dp[i][j]=Val.TRUE; 
        }
        return dp[i][j]=Val.FALSE;
    }
    
    public boolean isMatch(String s, String p) {
        Val[][] dp=new Val[s.length()+1][p.length()+1];
        for(Val[] row:dp) Arrays.fill(row,Val.UNKNOWN);
        return isMatch(s,0,p,0,dp)==Val.TRUE;
    }
}*/

DP: Bottom Up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isMatch(String s, String p) {
        int sLen=s.length(),pLen=p.length();
        boolean[][] dp=new boolean[sLen+1][pLen+1];
        dp[sLen][pLen]=true;
        for(int i=sLen;i>=0;i--){
            for(int j=pLen;j>=0;j--){
                boolean firstMatch=(i<sLen&&j<pLen) && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.');
                if(j+1<pLen && p.charAt(j+1)=='*'){
                dp[i][j]=dp[i][j+2]||firstMatch&&dp[i+1][j];
                }else{
                   if(j<pLen) dp[i][j]=firstMatch && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

0%