Wildcard Matching

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).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Solution

For the DP table

If the wildchard character is a '?', you just check n-1 and m-1 since ? matches with any character.
dp[n][m] = dp[n-1][m-1]
If the wildcard character is '*'.
a. Zero Occurrences of a character: If the current string matches the pattern till m-1 and there are 0 occurrences of any character for '*', it also matches till 'm'.
dp[n][m] = dp[n][m-1]
b. Non-Zero Occurrences of a character: str[0...(i)] will match wildcard[0...(j)] if str[0...(i - 1)] has matched wildcard[0...(j)].
dp[n][m] = dp[n-1][m]
If the wildcard character is neither '?' or '*':
If the string and wildcards have matched till now and if the characters at the current indexes match, we have a match.
dp[n][m] = dp[n-1][m-1] && strChar === wildcardChar

Code:

METHOD 2: BACKTRACKING

This is an intuitive technique where we only worry about "*" in the pattern. We have indexes for both the str and the pattern. We keep on matching and incremeneting both indexes.

If the pattern character is a "*". We save the current pattern and string indexes in temp variables. and the proceed with the loop assuming there are 0 occurrences for "*".

e.g. for str="abc" and pattern="a*c", when index is 1 for both str and pattern, we will first assume 0 occurrences for the * and just increment the pattern pointer and continue matching.

If there's a mismatch, we come back to the temp variables and assume 1 occurrence now.

Code:

The code is well commented:

PreviousRegular Expression Matching NextOptimal Paths To Target

Last updated 3 years ago

Was this helpful?

Solution

This is really similar to

For the DP table

If the wildchard character is a '?', you just check n-1 and m-1 since ? matches with any character.

dp[n][m] = dp[n-1][m-1]

If the wildcard character is '*'.

a. Zero Occurrences of a character: If the current string matches the pattern till m-1 and there are 0 occurrences of any character for '*', it also matches till 'm'.

dp[n][m] = dp[n][m-1]

b. Non-Zero Occurrences of a character: str[0...(i)] will match wildcard[0...(j)] if str[0...(i - 1)] has matched wildcard[0...(j)].

dp[n][m] = dp[n-1][m]

If the wildcard character is neither '?' or '*':

If the string and wildcards have matched till now and if the characters at the current indexes match, we have a match.

dp[n][m] = dp[n-1][m-1] && strChar === wildcardChar

METHOD 2: BACKTRACKING

This is an intuitive technique where we only worry about "*" in the pattern. We have indexes for both the str and the pattern. We keep on matching and incremeneting both indexes.

If the pattern character is a "*". We save the current pattern and string indexes in temp variables. and the proceed with the loop assuming there are 0 occurrences for "*".

e.g. for str="abc" and pattern="a*c", when index is 1 for both str and pattern, we will first assume 0 occurrences for the * and just increment the pattern pointer and continue matching.

If there's a mismatch, we come back to the temp variables and assume 1 occurrence now.