我写了下面的算法,它非常可怕,但目前这是我能够解决问题的唯一方法。我只是想知道这个方程的大o是什么。我猜是的 O(n!)
因为我把环放在 filter
功能。这是正确的吗?
/*
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;
暂无答案!
目前还没有任何答案,快来回答吧!