Алгоритм, чтобы сказать, сколько различных, ведущих символов необходимо, чтобы отличить слово из списка?

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

Более эффективный подход может заключаться в том, чтобы хранить ваш набор слов в структуре дерева, а не в списке.Это иерархическая структура, где каждый узел содержит префиксные символы своих дочерних элементов.Это означает, что вам не нужно сравнивать все слова - как только найден определенный префикс, который соответствует словам без необходимости префикса.

Хотя для 50 слов скорость вряд ли будет проблемой,Три позволит вам свести к минимуму количество необходимых сравнений символов, и вы можете отслеживать количество символов по мере продвижения по иерархии.

Если абсолютная эффективность является требованием, то точный способ организации дерева может стать важным, например, он может быть организован так, чтобы быть эффективным с учетом фактической статистики поисков, выполненных против него.

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;
}