題目描述
給定：
- 一個字典（可用單字集合）
- 一個不含空格的字串
請回傳一個插入空格後的字串，使每段都在字典中。
範例
字串: "bloombergisfun"
字典: ["bloom", "bloomberg", "is", "fun"]
輸出: "bloomberg is fun"
解題思路
這是典型 Word Break 問題。穩健解法是：
dp[i]表示s[:i]是否可被切分parent[i]記錄上一次切分位置，用於回溯重建答案
Python（DP + 重建）
def word_break_one(s: str, word_dict: list[str]) -> str:
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
parent = [-1] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
parent[i] = j
break
if not dp[n]:
return ""
parts = []
i = n
while i > 0:
j = parent[i]
parts.append(s[j:i])
i = j
return " ".join(reversed(parts))
複雜度
- 時間：
O(n^2) - 空間：
O(n)
需要面試輔助服務？聯絡 OA VO Service
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。