Wildcard Matching using C++
This article is going to be about the wildcard matching problem on leetcode. Just like my previous blog, the approach I will use to solve this problem will be Dynamic Programming.
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).
The Approach:
If you have solved the regular expression problem on leetcode, you will have no difficulty in understanding the solution to this problem. If not, you can check this blog out.
Coming back to the problem , in the pattern string, if you encounter a ‘*’, you would probably check by putting various characters in place of ‘*’ to check if the string is being satisfied. If encountered a ‘?’, check if the string is being satisfied until ‘?’ index. If it is, then the string is being satisfied; if not, then false.
The key point to use Dynamic Programming is to break down the problem into smaller sub problems and use the solutions to these sub problems to get the optimal solution to the main problem.
Here, we will make a 2D vector A with size (p_len+1 * s_len+1), p_len representing the length of the pattern and s_len representing the length of the string.
The rules for regular expression matching are:
if p[i-1] == ‘*’ : check one row up, one column left and diagonally up because if the string is being satisfied until now, its going to be satisfied as * can take any value any number of times.
if p[i-1] == s[j-1] : check diagonally up because if the string is being satisfied until now, its going to be satisfied as the characters are being matched.
if p[i-1] == ‘?’ : check diagonally up because if the string is being satisfied until now, its going to be satisfied as ? can take any one character.
The first column and the first row are not the part of the string. This is the reason that vector A is of size(p_len+1 * s_len+1). The blank space satisfies another blank regex, thus A[0][0] is True.
The whole vector A is filled referring to the above mentioned rules and the last index of this 2 D vector determines whether there is a match or not.
The Code:
I hope this article would have helped you.
Enjoy and stay tuned! Let the code begin!!
