Fast anagrams checker algorithm (HackerRank)

user_7917815 0
Viewed 1258

Problem:

Given two arrays of strings, for every string in list (query), determine how many anagrams of it are in the other list (dictionary). It should return an array of integers.

Example:

query = ["a", "nark", "bs", "hack", "stair"]
dictionary = ['hack', 'a', 'rank', 'khac', 'ackh', 'kran', 'rankhacker', 'a', 'ab', 'ba', 'stairs', 'raits']

The answer would be [2, 2, 0, 3, 1] since query[0] ('a') has 2 anagrams in dictionary: 'a' and 'a' and so on...

This was the code I came up with:

function sortArray(array) {
    let answer = [];
    for(let i = 0; i< array.length ; i++) {
         let data = array[i].split('').sort().join('');
         answer.push(data);
    }
    return answer;
}

function stringAnagram(dictionary, query) {
    // Write your code here
    let sortedDict = sortArray(dictionary);
    let sortedQuery = sortArray(query);
    let answer = [];
    console.log(sortedDict.length);
    console.log(sortedQuery.length);
    sortedQuery.map(data => {
        let i = 0;
        sortedDict.forEach(dictData => {
            if(data === dictData)
                i++;
        })
        answer.push(i);
    })

    return answer;
}

However it is returning timeout error for longer test cases. Need some help optimizing it. Any suggestions? I'm trying to achieve it in JavaScript.

anagram algorithm javascript
2 Answers

You may want to avoid using (expensive) Array.prototype.sort() to detect anagram and give your anagram detection algorithm as much shortcuts as possible.

So, if assume, anagrams should be the strings of the same length with the same count of the same characters, you may go something, like that:

const  query = ["a", "nark", "bs", "hack", "stair"], 
        dictionary = ['hack', 'a', 'rank', 'khac', 'ackh', 'kran', 'rankhacker', 'a', 'ab', 'ba', 'stairs', 'raits'],
        
        charCount = s => [...s].reduce((acc,c) => 
          (acc[c]=(acc[c]||0)+1, acc), {}),
          
        areAnagrams = (s1, s2) => {
          if(s1.length != s2.length) return false
          const s1CharCount = charCount(s1),
                s2CharCount = charCount(s2),
                result = Object
                  .keys(s1CharCount)
                  .every(char =>
                    s2CharCount[char] == s1CharCount[char])
          return result
        },
        
        outcome = query.map(word =>
          dictionary
            .filter(_word => areAnagrams(word, _word))
            .length
        )
            
console.log(outcome)

user_112990530

Slightly more verbose way of doing it - but it works and makes sense to me - for each word in the original array, find the words in the target array that are the same length and then count those that are anagrams of the original word (an anagram is another word made up of the same letters in any order).

So the steps are -

Iterate over the firat array and for each word - filter the target array to get all words that are the same length as that word (potentialAnagrams)

Then iterate over that potentialAnagrams array and pass each word to a function that checks if all the letters and only the letters in the original word are present (in the given example - that would be [2, 2, 0, 3, 1]

Add up all anagrams of the word and pass the count to an array that is logged as the final result.

const  queryArr = ["a", "nark", "bs", "hack", "stair"];
const dictionaryArr = ['hack', 'a', 'rank', 'khac', 'ackh', 'kran', 'rankhacker', 'a', 'ab', 'ba', 'stairs', 'raits'];

let anagramsArr = [];

queryArr.forEach(function(query){
  let anagramsCount = 0
  const potentialAnagrams = dictionaryArr.filter(el => el.length === query.length);

  potentialAnagrams.forEach(function(potentialAnagram){
     if(isAnagram(query,potentialAnagram)){
      anagramsCount++
     }
   })
  anagramsArr.push(anagramsCount);
})

function isAnagram(word1, word2){
  let count = 0;
  const word1Arr = word1.split('');
  const word2Arr = word2.split('');
  
  if( word1Arr.length !== word2Arr.length) {
     return 'Invalid data - words 1 and 2 are of different lengths';
  }
  
  word1Arr.forEach(function(letter){
    if(word2.indexOf(letter) !== -1) {
     count++
    }
  })
    return count === word1Arr.length
}
console.log(isAnagram('ab', 'bab')); //gives 'Invalid data - words 1 and 2 are of different lengths';

console.log(anagramsArr); //gives [2, 2, 0, 3,1];

user_58675720
Related