HardRating 1882
1255. Maximum Score Words Formed by Letters
arrayhash-tablestringdynamic-programmingbacktrackingbit-manipulationcountingbitmask
解題說明
Maximum Score Words Formed by Letters
題目描述： 給定一組單詞 words、可用字母 letters（每個字母只能用一次）和每個字母的分數 score。選擇一個單詞子集，使得所有選中單詞能用可用字母拼出，且總分數最大。
解題思路：
- 位元遮罩枚舉：單詞數量最多 14，可以用 2^14 = 16384 個狀態枚舉所有子集。
- 對每個子集，檢查可用字母是否足夠拼出所有選中的單詞。
- 如果足夠，計算該子集的總分數，更新最大值。
- 也可以用回溯法（DFS）來枚舉子集，效果相同。
- 預處理每個單詞的字母需求可以加速檢查。
C++ 解法
複雜度分析
時間複雜度：O(2^n * n * 26) — 枚舉所有子集，檢查每個子集的字母需求
空間複雜度：O(n * 26) — 預處理每個單詞的字母頻率
虛擬碼
1. Count available letter frequencies 2. Precompute each word's letter frequency and score 3. For each subset (bitmask from 0 to 2^n - 1): a. Compute total letter needs and total score for selected words b. Check if needs <= available for all 26 letters c. If valid: update max score 4. Return max score
其他解法
-
回溯法（DFS）：對每個單詞決定選或不選。維護當前可用字母和累積分數。如果剩餘字母不夠拼當前單詞，剪枝跳過。比暴力枚舉所有子集更早剪枝。
-
動態規劃（字母狀態壓縮）：如果字母種類少，可以將可用字母的狀態壓縮為 DP 的鍵。但由於字母數量可變，壓縮效率不如直接枚舉子集。
延伸思考
- 如果單詞可以重複選擇（不限次數），問題變成什麼？如何求解？
- 如果單詞數量很大（例如 1000 個），但可用字母很少，有什麼優化策略？
- 如果每個字母的分數可以為負數，算法是否仍然正確？