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

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, если расстояние Левенштейна равно 1, и 0 в противном случае). Нет способа избежать этого.

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

Answer 2

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

В худшем случае все слова являются соседями.Пример 6 слов = {кот, толстый, крысиный, матовый, сат, на}.

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

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