題目描述:給定字串陣列,將所有變位詞分組,回傳所有分組。
解題思路:將每個字串排序後作為雜湊表的鍵(所有變位詞排序後相同),將原字串加入對應的值列表中。最後將所有值列表匯集成結果。排序每個字串需 O(k log k)(k 為平均長度),整體 O(nk log k)。另一種方法用字元頻率(26 個計數)作為鍵,避免排序。
時間複雜度:O(nk log k),n 為字串數,k 為平均長度 — 每個字串排序 O(k log k)。
空間複雜度:O(nk) — 雜湊表儲存所有字串。
1. Create hash map: sorted_string -> list of original strings 2. For each string s: a. key = sorted(s) b. groups[key].append(s) 3. Return all values from groups
排序後分組 O(nk log k):為每個詞排序後作為鍵,時間複雜度更差。
質數乘積 O(nk):將字符與質數相乘以計算雜湊值,易錯誤且空間複雜。