← Back to all recaps
VO Bloomberg

Bloomberg Interview Question: Expand a Binary String with Wildcards

1 min read

Problem

Given a binary string that may contain one or more wildcards ?, generate all possible strings by replacing each ? with 0 or 1.

Examples:

"01?0" -> 0100, 0110
"01??" -> 0100, 0101, 0110, 0111
"0?1"  -> 001, 011

Approach

Classic DFS / backtracking:

  • If the current char is 0/1, keep it.
  • If it is ?, branch into two paths (put 0 and put 1).

Python (backtracking)

def expand(s: str) -> list[str]:
    res = []

    def dfs(i: int, cur: list[str]):
        if i == len(s):
            res.append(''.join(cur))
            return

        if s[i] == '?':
            for c in ('0', '1'):
                cur.append(c)
                dfs(i + 1, cur)
                cur.pop()
        else:
            cur.append(s[i])
            dfs(i + 1, cur)
            cur.pop()

    dfs(0, [])
    return res

Complexity

If there are k wildcards, there are 2^k outputs.

  • Time: O(n * 2^k)
  • Space: O(n * 2^k) to store results

Need interview help? Contact OA VO Service

Need real interview questions? Contact WeChat: Coding0201 to get the questions.

联系方式

Email: [email protected] Telegram: @OAVOProxy