題目描述:
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);
}
}