[LeetCode刷題筆記] 49 - Group Anagrams

題目描述：

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lower-case English letters.

一刷題解（Dictionary）：

這一題給了我們一個數組，這個數組裡有n組字符都一樣但次序不同的字符串，我們需要將這些組合找出來並分別組成一個數組返回出去。我們首先要為各組字符設置一個合適的鍵，然後我們通過這個鍵再對所有字符進行遍歷和分類處理。我們知道同一組下的字符串的字符都是一樣的，唯一不同的就是字符的位置，因此我們只要把它們重新排序一次就可以了。

排序完之後就能得一個這個字符串所屬組的「識別符」，然後根據這個「識別符」分類到字典裡，最後再遍歷字典的鍵，把不同組別的字符串放到結果數組裡。

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {
        //Key: 所屬組別識別; Value: 該組的字符串列表
        Dictionary<string, List<string>> sortedStrDict = new Dictionary<string, List<string>>();
        List<IList<string>> res = new List<IList<string>>();

        for (int i = 0; i < strs.Length; i++)
        {
            //得到當前字符串的所屬組別識別符
            string sortedStr = SortString(strs[i]);
            if (sortedStrDict.ContainsKey(sortedStr))
            {
                sortedStrDict[sortedStr].Add(strs[i]);
            }
            else
            {
                sortedStrDict.Add(sortedStr, new List<string>() { strs[i] });
            }
        }

        foreach (var key in sortedStrDict.Keys)
        {
            res.Add(sortedStrDict[key]);
        }

        return res;        
    }
    
    //對字符串排序，不同次序、字符一樣的字符串重新排序後的結果是一樣的。
    //因此，通過重新排序就可以知道哪些字符串屬於哪一組。
    string SortString(string str)
    {
        char[] arr = str.ToCharArray();
        Array.Sort(arr);
        return new string(arr);
    }   
}