PPractick

The problem

You're building a file search utility for an internal dev tool, similar to shell globbing (ls *.txt, find file?.log). Given an input string s and a pattern p containing wildcard characters ? (matches any single character) and * (matches any sequence of characters, including the empty sequence), implement a function that returns whether s matches p entirely (not just a substring match).

Function signature

bool isMatch(string s, string p);

Test cases

Input s	Input p	Output	Explanation
"aa"	"a"	false	p is too short to cover all of s
"aa"	"*"	true	* matches the entire string, including everything
"cb"	"?a"	false	? matches 'c', but 'a' doesn't match 'b'
"adceb"	"*a*b*"	true	* matches empty before a, dce between a and b, empty after b
"acdcb"	"a*c?b"	false	No valid alignment satisfies the pattern
""	""	true	Both empty — trivially matches
""	"*"	true	* can match the empty sequence
""	"?"	false	? requires exactly one character, but s is empty
"mississippi"	"m??*ss*?i*pi"	false	Classic tricky LeetCode edge case — verify with code

(Always double check patterns with consecutive *s or trailing *s against empty suffixes — common source of off-by-one bugs.)

How interviewers phrase it

• "Implement wildcard pattern matching supporting ? and *, similar to shell-style globbing."
• "Given a string and pattern, determine if the pattern matches the entire string." (emphasis on entire — not a substring/contains check).
• They may explicitly contrast it with Regular Expression Matching (LeetCode 10) to see if you conflate the two — * here means "any sequence," not "zero or more of the preceding character."

Clarifying questions to ask

1. Does * match an empty sequence too, or must it match at least one character?
2. Does the pattern need to match the entire string, or just find a matching substring?
3. Can s or p be empty? What should happen in those cases?
4. Is this the shell-glob style (* = any sequence, ? = any single char), or the regex style (* = zero-or-more of preceding char)? — explicitly confirm, since this is the #1 point of confusion with LeetCode 10.
5. What's the expected size of s and p? (Signals whether O(n·m) DP is acceptable or if the O(n+m) greedy two-pointer approach is expected.)

Follow-ups to expect

1. "Can you do this with O(1) or O(min(n,m)) space instead of O(n·m)?"
2. "How is this different from Regular Expression Matching (LeetCode 10)?"
3. "Can you solve it with a greedy approach instead of DP?"
4. "What if consecutive *s appear in the pattern?"
5. "Can you prove the greedy approach's correctness/termination?"
6. "What's the worst-case time complexity of the greedy approach?"

Related questions

• Longest common subsequence Hard
• Print Longest Common Subsequence Hard
• Longest common substring Hard
• Longest palindromic subsequence Hard
• Minimum insertions to make string palindrome Hard
• Minimum insertions or deletions to convert string A to B Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in