Question
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", "c*a*b") → false
</div>
Stats
| Frequency | 3 |
| Difficulty | 5 |
| Adjusted Difficulty | 5 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This question is similar to “Regex Matching”, and in fact can be solved using similar (DFS recursion) approach. This blog has the best analysis and solutions.
The solution is DP. The equation is not very difficult to write, but keep in mind to check character count before entering the algorithm. Failing to do so results in TLE.
My code
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return true;
}
// pre-check
int count = 0;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i)!='*') count++;
}
if(count > s.length()) {
return false;
}
// end of pre-check
int m = s.length();
int n = p.length();
// note the order is n,m,
// cuz we match each chars of p with chars of s
boolean[][] dp = new boolean[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (i == 0 && j == 0) {
dp[i][j] = true;
} else if (i == 0) {
dp[i][j] = false;
} else if (j == 0) {
// there is a special case: ("", "*")
if (p.charAt(i - 1) == '*' && dp[i-1][j]) {
dp[i][j] = true;
} else {
dp[i][j] = false;
}
} else if (p.charAt(i - 1) != '*') {
if (dp[i-1][j-1]) {
if (p.charAt(i - 1) == '?' || p.charAt(i - 1) == s.charAt(j - 1)) {
// single char matches
dp[i][j] = true;
}
}
} else {
// current char from p is a star
// find the first place at which p matches with s
int pos = 0;
while (pos <= m && !dp[i-1][pos]) {
pos++;
}
// starting from pos, all subsequent substring of s matches p
while (pos <= m) {
dp[i][pos++] = true;
}
// important to break the for loop here and do not check for row i any more
// this requires changing the nested loop to put j outside of i
// the execution time decrease from TLE/1800ms to 800ms by adding this line
break;
// this break finished off all check for row i, and i advance to next row
}
}
}
return dp[n][m];
}
}