Given an array of strings, group anagrams together.
For example, given:["eat", "tea", "tan", "ate", "nat", "bat"]
Return:
|
1 2 3 4 5 |
[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] |
Note: All inputs will be in lower-case.
Solution – Two strings are anagrams if both have same characters and count of each character to be same. In other words, they are shuffled version of one another. example – eat, tea, ate are anagrams
Actual definition – https://en.wikipedia.org/wiki/Anagram
If we sort anagrams then they will output same string.
Algorithm –
- iterate over an array of strings.
- initiate an empty object res to maintain a group of anagrams
- for each string check if it sorted version exists in res
- if sorted value exists, push the string corresponding to sorted value
- if it does not exist, add sorted value to res and then push the string corresponding to sorted value.
- Iterate over each property of res and then sort and push corresponding array to result set.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
var sortAlphabets = function(text) { return text.split('').sort().join(''); }; var groupAnagrams = function(strs) { var result = []; var res = {}; for(i=0; i<strs.length; i++) { var currentAna = sortAlphabets(strs[i]); if(res[currentAna]) { res[currentAna].push(strs[i]); } else { res[currentAna] = [strs[i]]; } }; var result = []; for (var key in res) { if (res.hasOwnProperty(key)) { result.push(res[key].sort()) } } return result; }; |
Run Code Result:
Your input
|
1 |
["eat","tea","tan","ate","nat","bat"] |
Your answer
|
1 |
[["ate","eat","tea"],["nat","tan"],["bat"]] |
Expected answer
|
1 |
[["ate","eat","tea"],["nat","tan"],["bat"]] |