[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);
  }  
}