Построение графа «смежных» строк

Question

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

Для строк A и B называются смежно если путем добавления, удаления или замены одного символа из A (в любой позиции), вы получите B.

Например scar и car смежны (удаление s от scar), поэтому являются car и far (замена c с f) и поэтому far и farm (добавление m).

Можно ли это сделать менее чем O(n^2)?

Answer 1

Вы должны вычислить n(n - 1)/2 = O(n^2) записей в матрице смежности (записи 1, если Levenshtein distance равно 1 и 0 в противном случае). Невозможно избежать этого.

(Обратите внимание, что данный n, я могу найти алфавит и набор слов на этом алфавите, что все n слов являются соседями, и график будет полным.)

Answer 2

Я думаю, что это невозможно.

В худшем случае все слова являются соседями. Пример 6 слов = {cat, fat, rat, mat, sat, at}.

В этом примере вам необходимо установить (n) * (n-1)/2 = 6 * 5/2 = 15 ребер.

Итак, вам нужны операции O (n^2), чтобы настроить края в худшем случае ... независимо от того, сколько циклов или циклов вам нужно, вы не можете улучшить это.