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
First Solution is recursive. Good for concept, but not efficient enough to pass large test sets:
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (*p == '*'){//return true;
while(*p == '*') ++p;
if (*p == '\0') return true;
while(*s != '\0' && !isMatch(s,p)){
++s;
}
return *s != '\0';
}
else if (*p == '\0' || *s == '\0') return *p == *s;
else if (*p == *s || *p == '?') return isMatch(++s,++p);
else return false;
}
};
Dynamic Programming, iteration version, both time and memory efficient:
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (!*s && !*p) return true;
int ms_max = 1;//size of *s
const char* ss = s;
while(*ss){ ++ms_max;++ss;}
int np_max = 1;
const char* pp = p;
while(*pp){if(*pp!='*')++np_max;++pp;}
if(ms_max < np_max) return false;
vector<vector<bool> > r(2, vector<bool>(ms_max, false));
bool flag = 1;
r[0][0] = true;
do{//*p
int ms = 1;
ss = s;
if (*p == '*'){
while(*p == '*') ++p;
--p;
r[flag][0] = r[!flag][0];
for( ;ms <= ms_max; ++ms){//up and left
if (r[!flag][ms] || r[flag][ms-1]) break;
else r[flag][ms] = false;
}
for(;ms <= ms_max; ++ms){
r[flag][ms] = true;
}
}
else{
do{
bool r_flag = false;
if (*ss == *p || *p == '?'){
r_flag = r[!flag][ms-1];//diagnal
}
r[flag][ms]=r_flag;
++ms;++ss;
}while(*ss);//*s
r[flag][0] = false;
}
++p;
flag = !flag;
}while(*p);
return r[!flag][ms_max-1];
}
};
The thinking process:
The recursive method is intuitive and gives great insight of the matching process. If we neglect the boundary cases for a moment, there are three basic cases when we try to match the characters in s[] and p[]:
1. No match. Simply return false. This is the last case in the program.
2. Single match. Either *s == *p, or *p == '?'. The return value of this case depends on the result of the rest parts of both s[] and p[] (recursion call), which start at the 'diagonal' position by advancing both s[] and p[] by 1 (++s, ++p)
3. Star case, i.e. when *p == '*'. This is where the complication comes in. A star can match 0, 1, 2, ..., to the end of string s[]. So, as long as one of the substrings match (recursion call), after advance over *, it returns true. This case returns false only after exhausting all possible substrings without a match.
After we have some sense on the dependencies of each step, learned from the recursive function calls, we can set up our dynamic programming frame. For example s[] = "abcdef" and p[] = "a?c*f"
The strings are indexed 1 for convenience. Now let's directly apply the rules learned from the recursion method:
The arrow means "depends on" or "recursion call". The cells without a match can be pre-filled with FALSE's. The tail cell '\0' '\0' is marked TRUE.
We eventually want to know cell(0,0), but we have to know cell(1)first;
s[1] == p[1] gives case 2, so cell(1) depends on cell(2);
p[2] == '?' gives case 2, so cell(2) depends on cell(3);
s[3] == p[3] gives case 2, so cell(3) depends on cell(4);
p[4] == '*' gives case 3, so cell(4) depends on all the crimson shaded cells. As long as one of the shaded cells is TRUE, Cell(4) is TRUE.
...
p[5] == s[6] gives case 2, so cell(5) depends on the tail '\0','\0' case, which is TRUE. So cell(5) = TRUE.
Then we trackback, just as the recursive functions.
cell(0) = cell(1) = cell(2) = cell(3) = cell(4) = cell(5) = TRUE.
At last the function returns TRUE.
The steps above is using dynamic programming matrix, but follow the recursion process. Now we do the REAL dynamic programming. Note that the problem is symmetric, which means you can match the strings from left to right, or from right to left, they are identical. In the recursion method, the actual result propagates from the bottom right corner to the up left corner. In dynamic programming, we want to start with row one, so we can flip the whole dependency graph. Again the arrows mean dependencies, or get value from.
All the non-matching cells are pre-filled with FALSE's. The only initial TRUE is at cell(0), which is also the case when you match two NULL strings. So now you just need a matrix size(s)*size(p), and fill the cells row by row according to the three rules:
1. No matching: fill FALSE;
2. Matching, or '?': copy the value from previous diagonal cell
3. '*': Look up all cells to the left, and look up the cells to the left of previous row, and the cell directly above ---- if there is at least one TRUE, fill TURE; otherwise fill FALSE
Finally return the value of the last cell.
There are some more tricks in practice.
Firstly, successive '*' is equivalent to a single '*', so we may suppress them together. After doing this, the number of '*'s is at most size(p)/2. So the worst run time is O(m*n + m^2), where m=size(p) and n=size(s).
Also consider that after removing all '*'s, size(p) <= size(s), which means m is at most 2n for the worst case, so that m = O(n). Thus the worst run time is O(m*n).
Secondly, the matrix is updated row by row, and even the '*' case requires two latest rows. So it is possible to have a space efficient way solve the matching problem by using two size(s) arrays.
