DEV Community

Clark Ngo
Clark Ngo

Posted on

How to solve Group Anagrams problem

Follow Me, Shout Out, or Give Thanks!

Please 💖 this article. a small thing to keep me motivated =)
Twitter: @djjasonclark
Linkedin: in/clarkngo

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.

Let's work with the following:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Enter fullscreen mode Exit fullscreen mode

Trial 1 - Not efficient:

  1. (plus space) copy input
["eat","tea","tan","ate","nat","bat"]
Enter fullscreen mode Exit fullscreen mode
  1. (plus time) sort copied input
["aet", "aet", "ant", "aet", "ant", "abt"]
Enter fullscreen mode Exit fullscreen mode
  1. (plus space and another space for map/dictionary and plus time) create list and assign same number to same words
[1,1,2,1,2,3]
Enter fullscreen mode Exit fullscreen mode

Well... let's just stop there.

Trial 2 - Hashing:

Hashing? The process of assigning a unique value to an object or attribute using an algorithm, which enables quicker access, is known as hashing.

  1. (plus space and time) iterate over each string and each of its character. in every loop, generate a "hash" by increase value at indices representing character (0 -> 'a', 1 -> 'b')

  2. once you have a hash, add that a key to a map/dictionary (key-> string, val-> list of strings). then insert word/s.

When you reach this.. you already know what to do. =)

Top comments (0)