題目描述:給定字串 s 和字典 wordDict,判斷 s 是否能被拆分成字典中的若干單詞(單詞可重複使用)。
解題思路:定義 dp[i] 表示 s[0..i-1] 是否可以被字典拆分。dp[0] = true(空字串)。對每個位置 i,檢查所有 j < i:若 dp[j] == true 且 s[j..i-1] 在字典中,則 dp[i] = true。將字典存入 unordered_set 以加速查詢。
時間複雜度:O(n³) — 雙層迴圈 O(n²),每次 substr 和雜湊查詢 O(n)。
空間複雜度:O(n + |dict|) — DP 陣列加字典集合。
1. Build hash set from wordDict
2. dp[0] = true; dp[1..n] = false
3. For i from 1 to n:
a. For j from 0 to i-1:
- If dp[j] == true and s[j..i-1] in dict:
dp[i] = true; break
4. Return dp[n]DFS 無記憶化 O(2^n) 最壞:遞迴嘗試所有切分點,無快取 — 重複計算。
BFS O(n²):視為圖搜尋,各位置為節點 — 同 DP 複雜度但空間用於隊列。