LeetCode - Wildcard Matching
Problem description
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
Analysis
The first thought is to use recursion like the problem Regular Expression Matching. However, this will result in a TLE.
To reduce calculation, a memorization is needed. So the first method is to use recursion and memorization.
And the second method is to use DP, which is equivalent to recursion with memorization.
The idea is to make pIndex a static value and fill all the cell for sIndex from 0 to end, and then update pIndex.
Here’s the code:
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
public class WildcardMatching {
public boolean isMatch(String s, String p) {
int sLen = s.length(), pLen = p.length();
// base cases
if (p.equals(s) || p.equals("*")) {
return true;
}
if (p.isEmpty() || s.isEmpty()) {
return false;
}
// init all matrix except [0][0] element as False
boolean[][] d = new boolean[pLen + 1][sLen + 1];
d[0][0] = true;
// DP compute
for (int pIdx = 1; pIdx < pLen + 1; pIdx++) {
// the current character in the pattern is '*'
if (p.charAt(pIdx - 1) == '*') {
int sIdx = 1;
// d[p_idx - 1][s_idx - 1] is a string-pattern match
// on the previous step, i.e. one character before.
// Find the first idx in string with the previous math.
while ((!d[pIdx - 1][sIdx - 1]) && (sIdx < sLen + 1)) {
sIdx++;
}
// If (string) matches (pattern),
// when (string) matches (pattern)* as well
d[pIdx][sIdx - 1] = d[pIdx - 1][sIdx - 1];
// If (string) matches (pattern),
// when (string)(whatever_characters) matches (pattern)* as well
while (sIdx < sLen + 1) {
d[pIdx][sIdx++] = true;
}
}
// the current character in the pattern is '?'
else if (p.charAt(pIdx - 1) == '?') {
for (int sIdx = 1; sIdx < sLen + 1; sIdx++) {
d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1];
}
}
// the current character in the pattern is not '*' or '?'
else {
for (int sIdx = 1; sIdx < sLen + 1; sIdx++) {
// Match is possible if there is a previous match
// and current characters are the same
d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1] && (p.charAt(pIdx - 1) == s.charAt(sIdx - 1));
}
}
}
return d[pLen][sLen];
}
}
Another method is to use Backtrack, see detailed explanation
What to improve
- substring or string matching => DP