一种算法可以告诉我们需要多少个不同的前导字符才能从列表中识别一个单词？

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 将使您能够最大限度地减少所需的字符比较数量，并且您可以在向下递归层次结构时跟踪字符计数。

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

Answer 2

对列表进行排序，然后迭代它，将每个单词与后续单词进行比较。与告诉您在发现差异之前必须检查多少个字符的例程进行比较。边走边跟踪最大“深度”。

edit — 一个根据前导字符告诉您两个单词的“相似性”的函数：

function similarity(w1, w2) {
  var i, l = Math.min(w1.length, w2.length);

  for (i = 0; i < l; ++i)
    if (w1[i] !== w2[i]) break;

  return i;
}