javascript——这个算法的一个大o是什么?

l3zydbqr  于 2021-09-13  发布在  Java
关注(0)|答案(0)|浏览(194)

我写了下面的算法,它非常可怕,但目前这是我能够解决问题的唯一方法。我只是想知道这个方程的大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;

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题