題目在問什麼

給一組字串，請把互為 anagram 的字串分在同一組。

anagram 的意思是：

  • 字母完全一樣
  • 只是排列順序不同

例子

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

解題思路

這題的核心是先替每個字串找一個「可以代表它所屬群組」的 key。

最常見的做法是：

  1. 把字串轉成字元陣列
  2. 排序
  3. 再轉回字串

排序後：

  • "eat" 會變成 "aet"
  • "tea" 也會變成 "aet"

所以它們就會落到同一組。

接著只要用 Dictionary<string, List<string>>：

  • key：排序後的字串
  • value：屬於這組的所有原字串

就能把答案收好。

為什麼排序後可以當 key

因為 anagram 的差別只在順序，不在字元組成。

只要把順序消掉，留下來的結果就會一樣。

所以：

  • 同組字串排序後一定相同
  • 不同組字串排序後通常不同

這就是這題最穩的分組依據。

代碼

public class Solution
{
    public IList<IList<string>> GroupAnagrams(string[] strs)
    {
        Dictionary<string, List<string>> groups = new Dictionary<string, List<string>>();

        foreach (string str in strs)
        {
            string sortedStr = SortString(str);

            if (!groups.ContainsKey(sortedStr))
            {
                groups.Add(sortedStr, new List<string>());
            }

            groups[sortedStr].Add(str);
        }

        List<IList<string>> result = new List<IList<string>>();

        foreach (List<string> group in groups.Values)
        {
            result.Add(group);
        }

        return result;
    }

    private string SortString(string str)
    {
        char[] arr = str.ToCharArray();
        Array.Sort(arr);
        return new string(arr);
    }
}

複雜度

假設共有 n 個字串，每個字串平均長度是 k：

  • 時間複雜度：O(n * k log k)
  • 空間複雜度：O(n * k)

這題先記住的重點

  • 分組題通常先想 key 要怎麼設計
  • anagram 題最常見的 key 就是排序後字串
  • Dictionary<key, List<value>> 是這類題目的標配