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
Webmaster (Zhang Jian): π
Hi everyone! I am Zhang Jian.
I know the challenge of transitioning from mastering algorithms to actually landing a great job. That's why, in addition to this resource, I personally developed
leader.me!
π leader.me is the ultimate all-in-one platform for programmers to build their personal brand, featuring portfolio hosting, resume builders, and integrated blogs.
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)
result = Hash.new([])
strs.each do |str|
result[str.chars.sort.join] += [str]
end
result.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
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 49. Group Anagrams. Thanks!Level Up Your Developer Identity
π While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend leader.me β the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- π Resume, Portfolio & Blog: Integrate your skills, projects, and writing into one stunning site.
- π Free Custom Domain: Bind your own personal domain for freeβforever.
- β¨ Premium Subdomains: Stand out with elite tech handle like
name.leader.me.