How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Citadel during technical interviews.

Match a string with wildcard pattern recursively

Company: Citadel

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a function that checks whether an input string matches a wildcard pattern. ### Pattern rules - `?` matches **exactly one** character. - `*` matches **any sequence** of characters, including the empty sequence. - All other characters match themselves. ### Input - A string `s` - A pattern string `p` ### Output - Return `true` if `s` matches `p` entirely (not a substring match), otherwise `false`. ### Examples - `s = "aa"`, `p = "a"` → `false` - `s = "aa"`, `p = "*"` → `true` - `s = "cb"`, `p = "?a"` → `false` - `s = "adceb"`, `p = "*a*b"` → `true` ### Constraints (typical interview assumptions) - `0 ≤ len(s), len(p) ≤ 2000` - You should discuss a recursive approach and how to avoid exponential blow-up.

Quick Answer: This question evaluates proficiency in string pattern matching, recursive problem decomposition, and algorithmic optimization including handling wildcard semantics and complexity analysis.

Implement a function that checks whether a string matches a wildcard pattern exactly. Pattern rules: - '?' matches exactly one character. - '*' matches any sequence of characters, including the empty sequence. - Any other character matches itself. The match must cover the entire string, not just a substring. A purely naive recursive solution can become exponentially slow because the same subproblems are recomputed many times. An efficient solution should use recursion with memoization (or equivalent dynamic programming) to avoid this blow-up.

Constraints

0 <= len(s), len(p) <= 2000
s and p consist of printable characters, where p may also contain '?' and '*'
The solution should avoid exponential recursion by caching repeated states

Examples

Input: ("aa", "a")

Expected Output: False

Explanation: The pattern 'a' matches only one character, so it cannot match the entire string 'aa'.

Input: ("aa", "*")

Expected Output: True

Explanation: The '*' wildcard can match any sequence, including 'aa'.

Input: ("cb", "?a")

Expected Output: False

Explanation: '?' matches 'c', but then 'a' does not match 'b'.

Input: ("adceb", "*a*b")

Expected Output: True

Explanation: The first '*' can match an empty prefix, the second '*' can match 'dce', and the remaining letters align.

Input: ("", "")

Expected Output: True

Explanation: An empty pattern matches an empty string.

Input: ("", "*")

Expected Output: True

Explanation: The '*' wildcard can match the empty sequence.

Input: ("", "?")

Expected Output: False

Explanation: '?' must match exactly one character, but the string is empty.

Input: ("abcde", "a*?e")

Expected Output: True

Explanation: 'a' matches 'a', '*' can match 'bc', '?' matches 'd', and 'e' matches 'e'.

Input: ("abc", "a**c")

Expected Output: True

Explanation: Consecutive '*' characters still behave like a wildcard sequence matcher, so this matches 'abc'.

Input: ("acdcb", "a*c?b")

Expected Output: False

Explanation: No way of expanding '*' makes the rest of the pattern match the entire string.

Hints

Think of each recursive state as a pair of indices: one in the string and one in the pattern.
If you memoize the answer for each (i, j), you can avoid recomputing the same wildcard decisions many times.

Quick Overview

This question evaluates proficiency in string pattern matching, recursive problem decomposition, and algorithmic optimization including handling wildcard semantics and complexity analysis.