49. Group Anagrams

Problem Statement

link: LeetCode.cn LeetCode

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:

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

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

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

Solution Approach

The approach is to use the sorted version of each string as a key to group anagrams together.

Algorithm

1. Initialize a dictionary to group words by their sorted key. Use the defaultdict from the collections module to simplify the process.
2. Iterate through each word in the input list, sort the word, and use this sorted string as the key in our dictionary. Add the original word to the list of values for that key.
3. After processing all words, the dictionary values will represent groups of anagrams. Return these groups as a list of lists.

Implement

    class Solution:
      def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
          dic = defaultdict(list)
          for s in strs:
              key = ''.join(sorted(s))
              dic[key].append(s)
          print(dic)
          return list(dic.values())

    
    

Twitter  facebook  Email