LeetCode 49. Group Anagrams

Description

https://leetcode.com/problems/group-anagrams/

Given an array of strings, group anagrams together.

Example:

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

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

Explanation

use sorted words to group anagrams

Python Solution

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = []
        
        groups = {}
        
        for word in strs:
            sorted_word = ''.join(sorted(word))
            if sorted_word in groups:
                groups[sorted_word].append(word)
            else:
                groups[sorted_word] = [word]
        
        for key, value in groups.items():
            result.append(value)
            
        return result
  • Time complexity: O(n).
  • Space complexity: O(n).

3 Thoughts to “LeetCode 49. Group Anagrams”

  1. /**
    Solution in java
    **/

    class Solution
    {
    public static void main(String[] args)
    {
    String[] strings = {“cat”, “dog”, “tac”, “god”, “act”};
    List output = groupAnagrams(strings);
    System.out.println(“output is: “+ output.toString());
    }

    private static List groupAnagrams(String[] strs)
    {
    Map map = new HashMap();
    for(String str : strs)
    {
    char[] curr = str.toCharArray();
    Arrays.sort(curr);
    String tmp = new String(curr);
    if(!map.containsKey(tmp))
    {
    map.put(tmp,new ArrayList());
    }
    map.get(tmp).add(str);
    }

    return new ArrayList(map.values());
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *