0

I wrote the following algorithm and it's pretty horrendous but at the moment it was the only way I was able to solve the problem. I was just wondering what the Big O of this equation is. My best guess is that it is O(n!) since I have the loops inside the filter function. Is this correct?

/*

Scrabble Validator, essentially.

const dictionary = ['apple', 'avocado', 'anteater', 'april', 'basket', 'ball', 'cat', 'cradle'] etc for about 100 or so words

const points = [{a:1}, {b:2}, {c:3}, {d:4}]; etc for all the letters in the alphabet. there are blanks - a blank is worth 0 but can be used in place of any letter

given a string of letters and a dictionary, 

1. find all valid anagrams 
2. find their point value using a Points object
3. Sort those valid options by highest scoring point

*/

const chars = 'aplpe';
const dictionary = ['apple', 'avocado', 'lap', 'app', 'anteater', 'april', 'basket', 'ball', 'cat', 'cradle'];
const points = [{p:1}, {a:2}, {e:3}, {l:4}];


let pointsMap = {};
points.forEach((point) => pointsMap = { ...pointsMap, ...point });

const charMap = {};
for (let char of chars) {
  charMap[char] = charMap[char] + 1 || 1;
}


const matches = dictionary
  .filter(word => {
    if (word.length > chars.length) return false;

    const wordMap = {};
    for (let char of word) {
      wordMap[char] = wordMap[char] + 1 || 1;
    }

    for (let char in wordMap) {
      if (!charMap[char] || charMap[char] < wordMap[char]) {
        return false;
      }
    }

    return true;
  })
  .map((word) => {
    let total = 0;
    for (let char of word) {
      total += pointsMap[char];
    }
    return { word, total }
  })
  .sort((a, b) => a.total > b.total ? -1 : 1)
  .map(({ word }) => word);

return matches;
JonnySins666
  • 65
  • 1
  • 5
  • what is it doing? do you have some examples and results? – Nina Scholz Jul 11 '21 at 15:57
  • @NinaScholz it's basically an algorithm for the "scrabble" board game, with the inputs in the problem in the comment the results would be `[ 'apple', 'lap', 'app' ]` because these are the 3 valid words you can make using the `chars` input `aplpe` and the `dictionary` input `['apple', 'avocado', 'anteater', 'april', 'basket', 'ball', 'cat', 'cradle']` and they are sorted by which words will give you the biggest to least score. – JonnySins666 Jul 11 '21 at 16:00
  • Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Welbog Jul 11 '21 at 21:58

0 Answers0