Total Accepted: 59407 Total Submissions: 335592 Difficulty: Hard

Implement wildcard pattern matching with support for ‘?’ and ‘’. ‘?’ Matches any single character. ‘’ Matches any sequence of characters (including the empty sequence).

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

The function prototype should be: bool isMatch(const char *s, const char *p)

Some examples: isMatch(“aa”,“a”) → false isMatch(“aa”,“aa”) → true isMatch(“aaa”,“aa”) → false isMatch(“aa”, “”) → true isMatch(“aa”, “a”) → true isMatch(“ab”, “?”) → true isMatch(“aab”, “ca*b”) → false

Hide Company Tags Google Snapchat Facebook Hide Tags Dynamic Programming Backtracking Greedy String Hide Similar Problems (H) Regular Expression Matching

 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

public class Solution {
    public boolean isMatch(String s, String p) {
        // ref: dp solution: https://www.youtube.com/watch?v=3ZDZ-N0EPV0
        char[] str = s.toCharArray();
        char[] pattern = p.toCharArray();
        
        // replace multiple * with one *
        // e.g. a***b***c --> a*b*c
        boolean isFirst = true;
        int writeIndex = 0;
        
        for (int i = 0; i < pattern.length; i++) {
           if (pattern[i] == '*') {
               if (isFirst) {
                    pattern[writeIndex++] = pattern[i];
                    isFirst = false;
                }
            } else {
                pattern[writeIndex++] = pattern[i];
                isFirst = true;
            }
        }
        
        // str - > row,  pattern -> col,  2D matrix, dp solution 
        /*  T[i][j]  =  (1) T[i-1][j-1]              if p[j] = ? || s[i-1] == p[j-1]
                        (2)  T[i][j-1] || T[i-1][j]  if p[j]=*
                        (3)  False                   if s[i] != p[j]
            Time complexity : O(m * n)   Space complexity : O(m * n)
            s = "xbylmz" , p = "x?y*z" --> true
        */
        boolean[][] T = new boolean[str.length + 1][pattern.length + 1];
        T[0][0] = true;
        
        if (writeIndex > 0 && pattern[0] == '*') {
            T[0][1] = true;
        }
        
        for (int i = 1; i < T.length; i++) {
            for (int j = 1; j < T[0].length; j++) {
                if (pattern[j-1] == '?'  || str[i-1] == pattern[j-1]  ) {
                    T[i][j] = T[i-1][j-1];
                } else if (pattern[j-1] == '*') {
                    T[i][j] =  T[i-1][j] || T[i][j-1];
                }
            }
        }
        return T[str.length][writeIndex];
    }
}