[Leetcode Solution] Wildcard Matching

GOOD PROBLEM

Analysis 

• Directly use DFS of course ETL
• Use DP also ETL
• f[i][j]=f[i-1][j-1](a[i]==b[j] || b[j]=='?')
• or
• f[i][j]=f[k][j-1](i<=k<=a.size())(b[j]=='*')

• PRUNING ONE: Knowing that if there are multiple consecutive * in the string b, then eliminate them and remain one * is ok. This pruning passes all the testcases except for the last one.

• PRUNING TWO: Another pruning comes up with this post. Here let me show the details about this.

Let f(p,q) denote if a[0..p] matches b[0..q]. Then our task is to find out the value of f(a.size,b.size()). The searching procedure of finding the answer is a tree structure like this.

Each node(p,q) will have one child if b[q]=='?' or a[p]==b[q], or multi children if b[q]=='*'. ( In the figure we can see that node(p,q) has multi children while node(p,q+1) has one child).
The subtle trick is if we reached the node say (p+2+2,q+1+2) then there is no need to search upper layer's nodes which circled by a dotted line. This can be proved by contradiction in following figure.

Let two lines denote the two strings a and b. Here b[q]=='*'. And we do the search to the q+1+t. Then we can know there is no need to do the remained search at q. Because if there is a possible solution from the remaining cases, there must be also a possible solution at the current scenario. Because the second '*' can fill the gap between A and B in above figure.

• PRUNING THREE. after two pruning above the program still is blocked at the last test case. So the last pruning comes that let aux(k) denote the number of alphabet in b[k..end]. If a search node(p,q) which a.size() - p < aux(q) then we know there won't be a solution from this point.

Note

Code