Расстояние Левенштейна с шифрованием символов?

Вы можете попробовать библиотеку difflib или внешнюю библиотеку под названием pylevenshtein.

Подсчитайте количество символов каждого типа (используя HashMap или эквивалент), затем вычтите полученные значения и возьмите абсолютное значение каждого вычитания. Сложите все это вместе, а затем разделите на 2 (потому что вы удвоили каждую разницу).

Пример:

banana
batman

a - 3 , 2 -> |1| -> 1
b - 1 , 1 -> |0| -> 0
m - 0 , 1 -> |-1| -> 1
n - 2 , 1 -> |1| -> 1
t - 0 , 1 -> |-1| -> 1

Следовательно, у вас есть 1+1+1+1 = 4 -> 4/2 = 2

Проверьте: в banana замените одну n на t и одну a на m (2 изменения), и у вас есть буквы в batman

Если строки имеют разную длину, рассчитайте разницу в длине строки, вычтите это число из вашего счетчика разностей (см. выше). Затем разделите на 2 и прибавьте это число обратно.

Пример:

nab
banana

total difference count: 3
3 - 3 = 0 -> 0 / 2 = 0 -> 0 + 3 = 3

Также я бы вообще не использовал Левенштейна здесь, потому что большая часть трудностей с этой проблемой связана с позиционированием, которое вас не волнует.

Решение для динамического программирования расстояния Левенштейна можно просто отредактировать, чтобы поймать попарное скремблирование, например, для дели, дели и придать этому меньший вес по сравнению с соответствующими заменами, добавлениями или удалениями.

Изменить: этот алгоритм уже существует и называется Расстояние Дамерау-Левенштейна . Поиск по этому алгоритму даст вам пакет Python, который вы можете использовать напрямую.