[LeetCode] 44. Wildcard Matching

Posted on | In

Problem

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

1
2
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like ? or *.

Example 1:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

1
2
3
4
5
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

1
2
3
4
5
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

1
2
3
4
Input:
s = "acdcb"
p = "a*c?b"
Output: false

Explanation

  1. We can use dynamic programming to solve this problem.

  2. First, if pattern p is empty and string s is also empty, then we return true.

  3. Basecase, leftmost column, we know that if p is not empty, but s is empty. Then we need to check if p has only one character and that character of p is *, if it is *, then it can be true. Else, it is false.

  4. Basecase, top row, if p is empty, but s is not empty, return false.

  5. If p’s current character match s’s current character, then its result is the same boolean check(p.substring(0, pCur-1), s.substring(0, sCur-1), in other word, same as top left corner result.

  6. Else if p’s current character is *, then we consider two cases: case1, * serves as empty, then we return boolean check(p.substring(0, pCur-1), s), in other word, same as top result. For example, p=abc* and s=abc.

  7. Case2, * serves as not empty, then we return boolean check(p, s.substring(0, sCur-1), in other word, same as left result. For example, p=abc* and s=abcde, the result is same as p=abc* and s=abcd, then p=abc* and s=abc.

  8. At the end, we can return the bottom right corner result.

Solution

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
class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] arr = new boolean[p.length()+1][s.length()+1];
        arr[0][0] = true;
        for (int i = 1; i < p.length()+1; i++) {
            if (p.charAt(i-1) == '*') {
                arr[i][0] = arr[i-1][0];
            }
        }
        
        for (int pInd = 1; pInd < p.length()+1; pInd++) {
            for (int sInd = 1; sInd < s.length()+1; sInd++) {
                if (p.charAt(pInd-1) == s.charAt(sInd-1) || p.charAt(pInd-1) == '?') {
                    arr[pInd][sInd] = arr[pInd-1][sInd-1]; //top left
                } else {
                    if (p.charAt(pInd-1) == '*') {
                        //top or left
                        arr[pInd][sInd] = arr[pInd-1][sInd] || arr[pInd][sInd-1];
                    }
                }
            }
        }
        
        return arr[p.length()][s.length()];
    }
}