2135. Count Words Obtained After Adding a Letter
解題說明
Count Words Obtained After Adding a Letter
題目描述：給定兩個字串陣列 startWords 和 targetWords。對 targetWords 中的每個單詞，判斷是否存在以下情況：從 startWords 中取一個單詞，加入某個不在該單詞中出現的字母，並重新排列所有字母後，可以得到該 targetWord。回傳滿足條件的 targetWord 數量。
注意：startWords 和 targetWords 中每個單詞的字母均不重複（可視為字母集合）。
解題思路：由於每個單詞字母不重複且只關心字母集合（與順序無關），可以用 位元遮罩（bitmask） 來表示每個單詞：第 i 位為 1 表示第 i 個字母存在。
對 startWords 的每個單詞計算其 bitmask，存入 HashSet。對 targetWords 的每個單詞，計算其 bitmask，然後嘗試「移除」其中的每一個字母（將對應位元清零），若清零後的 bitmask 在 HashSet 中存在，說明可以從某個 startWord 加一個字母得到此 targetWord，計數加一。此方法將字串操作轉換為整數位元操作，效率極高。
C++ 解法
複雜度分析
時間複雜度：O(N × L + M × L)，其中 N 為 startWords 數量，M 為 targetWords 數量，L 為單詞最大長度。建立 HashSet 需 O(N × L)，對每個 targetWord 最多嘗試 L 次位元操作和 HashSet 查詢，共 O(M × L)。整體線性於輸入大小。
空間複雜度：O(N)——HashSet 最多儲存 N 個整數 bitmask，每個佔用 O(1) 空間。由於字母僅有 26 個，bitmask 最多 26 位，均可存於一個 int。
虛擬碼
1. For each word in startWords:
a. Compute bitmask: set bit (c - 'a') for each character c.
b. Insert bitmask into a HashSet start_masks.
2. Initialize count = 0.
3. For each word in targetWords:
a. Compute target_mask similarly.
b. For each character c in the word:
- Compute reduced = target_mask XOR (1 << (c - 'a')).
- If reduced is in start_masks: increment count, break.
4. Return count.其他解法
方法一：Trie + 排列標準化 將每個單詞的字母排序後插入 Trie（因字母不重複，排序後可唯一表示字母集合）。對每個 targetWord 排序，再對每個位置嘗試刪除一個字母，在 Trie 中查找剩餘字母排序後的字串是否存在。時間複雜度 O(N × L log L + M × L² log L)，因排序和字串操作開銷更大，不如位元遮罩高效，但在字母集合更大（超過 26 字母）時 Trie 更具擴展性。
方法二：排序字串 + HashSet
將每個 startWord 的字母排序後存入 unordered_set<string>。對每個 targetWord 的排序版本，嘗試逐一刪除一個字元，在集合中查找。時間複雜度 O(N × L log L + M × L² log L)——每次刪除後仍需重新排序，比位元遮罩法慢一到兩個數量級。
方法三：雙向位元遮罩驗證
先建立 startWords 的 bitmask set，再對 targetWords 的每個 bitmask 檢驗其「減少一個位元」是否在 set 中。本質與主解相同，只是可進一步用 __builtin_popcount 預先過濾：若 popcount(target) - 1 != popcount(start) 則不符合（加一字母後位元數恰好多一）。此剪枝減少無效的 set 查詢。
延伸思考
- 若題目改為「刪除兩個字母後能否得到 startWord」，位元遮罩的枚舉複雜度如何變化？有無更快的方法？
- 如果單詞中字母可以重複（非唯一字母集合），位元遮罩方法是否仍然適用？需要如何修改資料結構？
- 將此題推廣：若 startWords 可以動態新增，每次新增後立即查詢某個 targetWord 是否可達，哪種資料結構最合適？