Coding

Wildcard matching

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string str and a pattern pat, implement a pattern matching function that supports the following special characters:

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

The pattern must match the entire string.

Input: str = "xaylmz", pat = "x?yz" Output: true **Explanation: ** The pattern "x?yz" matches the string "xaylmz":

'?' matches 'a'
'*' matches "lm"
'z' matches 'z'

Input: str = "xyza", pat = "xz" Output: false **Explanation: ** The pattern "xz" does not match the string "xyza" because there is an extra 'a' at the end of the string that is not matched by the pattern.

**Input: **str = "abc", par = "a?c"

0 <= length of(str, pattern) <= 200

cpp

class Solution {
public:
    bool wildCard(string str, string pat) {

    }
};

java

class Solution {
    public boolean wildCard(String str, String pat) {
       
    }

}

python

class Solution:
    def wildCard(self, str: str, pat: str) -> bool:

javascript

class Solution {
    wildCard(str, pat) {
    
    }
}

csharp

class Solution
{
    public bool WildCard(string str, string pat)
    {
       
    }

}

func wildCard(str, pat string) bool {

}

Stuck? Show a way to structure it+

01Define dp[i][j] for whether prefixes of s and pattern match.
02Match equal characters or `?` from the diagonal state.
03For `*`, combine matching empty (`dp[i][j-1]`) or one more character (`dp[i-1][j]`).
04Initialize the empty-string row so only all-star prefixes match.

Reference answer

Let dp[i][j] mean the first i characters of the text match the first j characters of the pattern. dp[0][0]=true. For a literal equal to the current text character, or ?, take dp[i-1][j-1]. For *, either let it represent empty (dp[i][j-1]) or consume the current text character and remain active (dp[i-1][j]). The empty text matches a pattern prefix only if that prefix consists entirely of *. Fill the table in O(nm) time and O(nm) space, or use two rows. Greedy backtracking can work in this exact wildcard language but is easier to get wrong; DP is the clearest general answer.

Then expect these follow-ups

How would you reduce the DP to O(m) space?
Tests: space optimization
When is the greedy two-pointer solution valid?
Tests: algorithm trade-offs

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question