Posts Regular Expression Match
Post
Cancel

Regular Expression Match

Problem Description

Implement wildcard pattern matching with support for ‘?’ and ‘*’ for strings A and B.

  • ’?’ : Matches any single character.
  • ‘*’ : Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

interviewbit

Solution

snapshot

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
60
61
62
63
64
65
66
public class Solution {

    public int isMatch(final String s, final String p) {
        
        int n = s.length();
        
        //consequtive start can be converted to a single star
        //can be optimized by using StringBuilder
        String pattern=p.charAt(0)+"";
        for(int i=1; i<p.length(); i++){
            if(p.charAt(i) == '*' && p.charAt(i-1) == '*') continue;
            pattern += String.valueOf(p.charAt(i));
        }
        
        int m = pattern.length();
        
        int[][] dp = new int[n][m];
        for(int i=0; i<n; i++){
            Arrays.fill(dp[i], -1);
        }
        
        matchHelper(s, pattern, n-1, m-1, dp);
        
        return dp[n-1][m-1];   
    }
    
    public int matchHelper(String s, String p, int i, int j, int[][] dp){
        
        if(i == -1 && j == -1) return 1;
        
        if(j == -1){ //i is not -1, so some characters are left without any match
            return 0;
        }

        if(i == -1){ //all characters exhausted but pattern has some left

            //if remaining character in pattern are all * then it's a match
            for(int k=0; k<=j; k++){
                if(p.charAt(k) != '*') return 0;
            }

            return 1;

        }

        if(dp[i][j] == -1){

            //if characters are matching of pattern has ?
            if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'){
                dp[i][j] = matchHelper(s, p, i-1, j-1, dp);

            //If pattern has *
            }else if(p.charAt(j) == '*'){

                //skip * as it can be empty OR match with single character and still keep it
                dp[i][j] = matchHelper(s, p, i, j-1, dp) | matchHelper(s, p, i-1, j, dp);
            }else{
                dp[i][j] = 0;
            }
        }

        return dp[i][j];

    }
    
}
This post is licensed under CC BY 4.0 by the author.