Fuck LeetCode > Array > 49. Group Anagrams > Solved in Python, Ruby > Repost or Contribute
LeetCode link: 49. Group Anagrams, difficulty: Medium.
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, 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 <= 10^40 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Intuition
Two strings,
batandatb, what is the fastest way to know that they are anagrams?Click to view the answer
Sort each string in alphabetical order, and then compare the sorted strings. If they are equal, then they are anagrams.
But after sorting, the original string is not taken into account, and the result is the grouping of the original string. How to solve it?
Click to view the answer
Use tuples, that is, put the alphabetically sorted string and the original string in a tuple, like this:
("abt", "bat").All that remains to do is to group this tuple array. What is the easiest way to group?
Click to view the answer
Use
Map,keyis the alphabetically sorted string, and value is the array of the original string.
Complexity
Time complexity
O(N * M * logM)
Space complexity
O(N)
Explanation
M = string.length
Python #
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
pairs = [(''.join(sorted(string)), string) for string in strs]
ordered_to_original = defaultdict(list)
for ordered, original in pairs:
ordered_to_original[ordered].append(original)
return list(ordered_to_original.values())
Ruby #
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
pairs = strs.map { |string| [ string.chars.sort.join, string ] }
ordered_to_original = Hash.new([])
pairs.each do |ordered, original|
ordered_to_original[ordered] += [original]
end
ordered_to_original.values
end
# Or solution 2: More concise way
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
strs.group_by { |string| string.chars.sort }.values
end