How to Group Anagrams Together in Separate Arrays

UpdatedDecember 21, 2021

•2 min read•View as Markdown

How to Group Anagrams Together in Separate Arrays

Eric Saupe

Comments

Join the discussion

No comments yet. Be the first to comment.

More from this blog

Compiling Frontend Assets with RSpec and Rails 7

Rails 7 ships with a lot of really great improvements to the frontend the biggest of which is removing webpacker in favor of a more generic approach to allow developers to use whatever they'd like to use to compile their assets like esbuild or import...

May 20, 20224 min read

Compiling Frontend Assets with RSpec and Rails 7

Rails System Tests with GitHub Actions

While working on Paylooza it was really important to me to have a very well tested application. Paylooza strives to be an affordable, off-the-shelf recurring billing solution for individuals and small businesses and because we are dealing with transa...

Jan 14, 20225 min read

Remote Debugging with Foreman and Byebug

With Rails 7 recently dropping there are a few improvements outside of the great new features that might take new projects by surprise. The first that I encountered after starting up a new Rails project was the bin/dev script that now uses foreman...

Dec 20, 20213 min read

Remote Debugging with Foreman and Byebug

Submit Client-side Compressed Images in a Form

Hobby projects are great because they can expose you to problems you've never encountered before. While working on Scavenger Hunt Party! I was noticing some issues in the real-world that were not present in my development environment. The biggest o...

Dec 4, 20215 min read

Submit Client-side Compressed Images in a Form

Eric Saupe's Blog

67 posts

Interview Question of the Week

https://buttondown.email/cassidoo/archive/almost-everything-will-work-again-if-you-unplug/

This week’s question: Given an array of strings, group the anagrams together in separate arrays. An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once.

Example:

$ groupAnagrams(["eat","tea","ten","poop","net","ate"])
$ [["poop"],["net","ten"],["eat","tea","ate"]]

Solution

Here is my ruby implementation of the solution. It works by summing the characters in each word to group them. Strings are simply arrays of characters and all characters have a value. By summing these characters we are left with a value for each word that can group words with the same value together.

words = ["eat","tea","ten","poop","net","ate"] words.group_by { |word| word.sum }.values [["eat", "tea", "ate"], ["ten", "net"], ["poop"]] # Here is how it groups them by their value words.group_by { |word| word.sum } {314=>["eat", "tea", "ate"], 327=>["ten", "net"], 446=>["poop"]}

This works pretty well, unfortunately it has some edge cases that could ruin it. For example, since we are summing the value of the characters we may group words that are wildly different but still have the same value. For example, the word "a" * 100 (which is just a word with 100 a's) would be equal to "d" * 97 (which is just a word with 97 d's) because "a" = 97 and "d" = 100 so the two words would both equal 9700. We can fix this by sorting the characters in the word and use those as the grouping key.

words = ["eat","tea","ten","poop","net","ate"] words.group_by { |word| word.chars.sort.join.to_sym }.values [["eat", "tea", "ate"], ["ten", "net"], ["poop"]] # Here is how it groups them by their sorted characters words.group_by { |word| word.chars.sort.join.to_sym } {:aet=>["eat", "tea", "ate"], :ent=>["ten", "net"], :oopp=>["poop"]}

This should handle all the edge cases that might appear. The only downside with this is sorting each word can get costly if the words are really big. Since this is just an exercise and I didn't want to spend too long on it I think this is good for now.

Did I miss anything? Is there a better solution? Probably. I'd love to hear about it!

Command Palette

Comments

More from this blog

Interview Question of the Week

Solution