DP #35. Wildcard Matching - mbhushan/dynpro GitHub Wiki
(35). Wild Card Matching.
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:
boolean isMatch(String string, String pattern)
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", "c*a*b") → false
Formula:
String []S = "xaybcdz";
String []P = "x?y*z";
if (S[i] == P[j] || P[j] == '?') {
T[i][j] = T[i-1][j-1];
} else if (P[j] == '*') {
T[i][j] = T[i-1][j] || T[i][j-1];
} else {
T[i][j] = false;
}
|
|
|
|
|
|
|
| (str, pat) |
0 |
x |
? |
y |
* |
z |
| 0 |
T |
F |
F |
F |
F |
F |
| x |
F |
T |
F |
F |
F |
F |
| a |
F |
F |
T |
F |
F |
F |
| y |
F |
F |
F |
T |
T |
F |
| b |
F |
F |
F |
F |
T |
F |
| c |
F |
F |
F |
F |
T |
F |
| d |
F |
F |
F |
F |
T |
F |
| z |
F |
F |
F |
F |
T |
T(match) |
Wildcard Matching
- Time Complexity: O(n * m)
- Space Complexity: O(n * m)