javascript - 一种算法来判断从列表中辨别单词需要多少个不同的前导字符？

Question

因此，如果您有一个包含 50 个单词的列表，并且您想了解读者必须看多深的单词才能算出所有独特的单词，您将如何做？

我基本上是在考虑将字符一个一个地加载到数组中，然后比较它们。不过，要比较的字符和数组太多了。我想知道什么是最有效的方法，如果已经有有效的方法？

我现在正在尝试使用 Javascript。

var words = [sort(prompt("Please, insert the word list", "default value in the text field"););];
var encr_int: Number=0;
for (i=0, j=0, maxdif=0; j < word.length; i++) {
    if(word[j].text.charAt(i) == word[j+1].text.charAt(i) AND i > maxdif) {
        maxdif = i;
    }
    else if(word[j].text.charAt(i) != word[j+1].text.charAt(i) {
        j+=1;
    }
    else if(word[j].text.charAt(i) == "") {
        i = 0;
    }
}
document.write(maxdif);

以上是我根据第一个答案写程序的努力。

Answer 1

一种更有效的方法可能是将您的单词集存储在 trie 结构而不是列表中。这是一个层次结构，其中每个节点都包含其子节点的前缀字符。这意味着您不必与所有单词进行比较 - 一旦发现某个前缀与没有该前缀的单词匹配，就需要将其删除。

虽然对于 50 个单词的速度不太可能成为问题，但 trie 将使您能够最大程度地减少所需的字符比较次数，并且您可以在向下递归层次结构时跟踪字符数。

如果绝对效率是一项要求，那么您组织 trie 的精确方式可能会变得很重要，例如，考虑到对其进行的搜索的实际统计数据，它可以组织得更高效。