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;