[FEATURE REQUEST] <Wildcard Matching>

[janmeshjs]

What would you like to Propose?

Wildcard Matching Algorithm is one of the most commonly seen algorithms while handling Strings with Dynamic Programming.

It is a string-matching problem where one can check if a given string matches a pattern that contains wildcards. Common wildcards include '*' (matches any sequence of characters) and '?' (matches any single character).
For example:

string1= "hello", string2 = "hllo"
"hello" and "hllo" match because * can match any characters, so it matches "e"

string1= "programming", string2 = "pr*?aing"
"programming" and "pr?a*ing" match because * can match "ogramm" and ? can match "o"

string1= "xyz", string2 = "*abc"
"xyz" and "*abc" do not match because * does not match different characters, and there is no matching character after *.

Issue details

The algorithm for the above mentioned Wildcard Matching is mentioned below:

We start with creating a 2D boolean array where dp[i][j] represents whether the first i characters in the pattern match the first j characters in the string.

• Initialize dp[0][0] to true because an empty pattern matches an empty string.
• If the pattern has '*', then it can match either:
• An empty string, in which case dp[i][j] = dp[i-1][j].
• Any character, in which case dp[i][j] = dp[i][j-1].
• For '?', it matches if the previous characters matched, so dp[i][j] = dp[i-1][j-1].
• For non-wildcard characters, they match only if the current characters match, so dp[i][j] = dp[i-1][j-1] && (pattern.charAt(i-1) == string.charAt(j-1)).

I've the code with the test cases ready. Assign me the issue to submit a pr.

Additional Information

No response

[Thanush19]

I can give efficient solution.. can u assign me @janmeshjs ??

[MadhurGupta979]

Hi @janmeshjs , I am a active leetcoder and i can provide the efficient solution for this problem with proper comments. Please Assign me this problem as i want to make a contribution.

[shaktimaan00]

Hi @janmeshjs , I have 3 years programming experience and still active at various coding platforms. I can provide a effective solution with clean comments. Please assign me this problem.