Created
November 19, 2019 15:36
-
-
Save PartyLich/a6f237862a442cab1c132cd35b180590 to your computer and use it in GitHub Desktop.
Hackerrank Sherlock and Anagrams
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // I opened the page one day and wrote the solution on another. I had forgotten it was in the dict/hashmap section... | |
| const sum = (acc, next) => acc + next; | |
| const matches = (val, i, arr) => { | |
| let count = 0; | |
| for (++i; i < arr.length; i++) { | |
| if (val == arr[i]) count++; | |
| } | |
| return count; | |
| }; | |
| // Complete the sherlockAndAnagrams function below. | |
| function sherlockAndAnagrams(s) { | |
| let strs = []; | |
| // get substring permutations | |
| for(let chunkSize = 1; chunkSize < s.length; chunkSize++) { | |
| let temp = []; | |
| // make array of sorted chunkSize substrings | |
| for(let i = 0; i <= s.length - chunkSize; i++) { | |
| temp.push(s.substr(i, chunkSize).split('').sort().join('')); | |
| } | |
| // count pairs | |
| temp = temp.map(matches) | |
| // add total | |
| strs.push(temp.reduce(sum)); | |
| } | |
| return strs.reduce(sum) | |
| } |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
It was 2 years ago and I don't really remember writing it, so I couldn't tell you what my thought process was at the time. I can try to work through what I may have been thinking:
So we've got 2 things to do: generate all the substrings, and determine which of them are anagrams
chunkSize(substring length) that increases from 1, and I slide the window along the array (of characters, aka a string) saving each as I go..sort()on ln 22 is in anticipation of the other part of the problem. Sorted arrays or strings are a) easier to compare and b) meet the anagram requirement when identical. Consider the pair 'abb' and 'bba' from the sample data. When sorted, they are 'abb' and 'abb'; identical strings.tempis a list of sorted substrings of the current chunk size.matches()maps each substring to the number of matching substrings i've stored (in other words, the number of pairs). So iftempis['a', 'b', 'b', 'a'], it maps to[1, 1, 0, 0][1, 1, 0, 0]reduces to2Hopefully that helps. Happy to elaborate as needed, when/if I have the free time to do so. It's worth noting that, as far as I can tell, I made no attempt at achieving efficiency. It looks like I got something that works and just left it at that. Readability may also be a concern.