-
Notifications
You must be signed in to change notification settings - Fork 0
/
WildCardMatching.java
71 lines (48 loc) · 1.63 KB
/
WildCardMatching.java
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
67
68
69
70
71
/*
Queston No. 44
Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Constraints:
0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.
*/
class Solution {
public boolean isMatch(String s, String p) {
final int m = s.length();
final int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 0; j < p.length(); ++j)
if (p.charAt(j) == '*')
dp[0][j + 1] = dp[0][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (p.charAt(j) == '*') {
final boolean matchEmpty = dp[i + 1][j];
final boolean matchSome = dp[i][j + 1];
dp[i + 1][j + 1] = matchEmpty || matchSome;
} else if (isMatch(s, i, p, j)) {
dp[i + 1][j + 1] = dp[i][j];
}
return dp[m][n];
}
private boolean isMatch(final String s, int i, final String p, int j) {
return j >= 0 && p.charAt(j) == '?' || s.charAt(i) == p.charAt(j);
}
}