DEV Community

Tammy Vo
Tammy Vo

Posted on

1

Group Anagrams

Leetcode Problem: Group Anagrams

Objective:

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.


Pattern: Arrays and Hashing


Approach:

  1. Create a 2D list for the result.
  2. Create a HashMap: key = sorted word, value = list of anagrams.
  3. Iterate through the input string array and sort the input.
  4. If the sorted input is not in hashmap or edge case where the sorted input equals the non-sorted input then add the sorted input as the key and the non-sorted input as an anagram.
  5. If the sorted input already exists as a key in the hashmap, then get the sorted key and add the non-sorted input into the anagram list.
  6. Iterate through the hashmap and add each anagram list into the result list. Return result.

Big-O Notation:

Time Complexity: O(m * nlog(n))
We have iterate n times for each string.
We sort each string using Arrays.sort() which is O(n log(n)).

Space Complexity: O(n * m)
We use additional data structures for storage.
We have a 2D list to store the result.
We have a hashmap to store elements.


Code:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // input: string array 
        // output: 2D list 
        List<List<String>> result = new ArrayList<List<String>>();

        Map <String, List<String>> hashMap = new HashMap<>();

        for(String str : strs){
            char [] array = str.toCharArray();
            Arrays.sort(array);

            String sortStr = str.valueOf(array);

            // edge case if current == key then add to key. 
            if(sortStr == str || !hashMap.containsKey(sortStr)){
                List <String> anagram = new ArrayList<>();
                anagram.add(str);
                hashMap.put(sortStr, anagram);
            } else {
                hashMap.get(sortStr).add(str);
            }
        }

        // add anagram list into result 
        for(String s : hashMap.keySet()){
            result.add(hashMap.get(s));
        }

        return result;
    }
}
Enter fullscreen mode Exit fullscreen mode

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more