題目描述
給定一個可能包含萬用字元 ? 的二進位字串，請列出所有可能結果：每個 ? 可以替換為 0 或 1。
例：
"01?0" -> 0100, 0110
"01??" -> 0100, 0101, 0110, 0111
"0?1" -> 001, 011
解題思路
典型 DFS / 回溯：
- 若是
0/1：直接加入 - 若是
?：分兩路，分別填0與1
Python 參考實作
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
複雜度
若有 k 個 ?，結果數量為 2^k。
- 時間：
O(n * 2^k) - 空間：
O(n * 2^k)（儲存所有輸出）
需要面試輔助服務？聯絡 OA VO Service
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。