Меньше всего перестановок букв

Сложная

На полке стоят таблички с буквами — это строка start. Нужно расставить их так, чтобы получилась строка goal. За один ход можно поменять местами любые две таблички. Строки состоят из одних и тех же букв (одна получается из другой перестановкой). Верните наименьшее число ходов, за которое start превращается в goal.

Пример 1

start="fade", goal="defa" → 2

Обмен букв 0 и 2 даёт "dafe", затем обмен букв 1 и 3 — "defa". Два обмена, одного не хватит.

Пример 2

start="abba", goal="baab" → 2

Обмен букв 0 и 1 даёт "baba", обмен букв 2 и 3 — "baab".

Пример 3

start="cab", goal="cab" → 0

Ограничения

1 ≤ len(start) ≤ 20
len(goal) == len(start)
строки состоят только из букв a–f
goal — перестановка букв start

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Breadth-First Search String

Вход

start="fade", goal="defa"

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 46 тестов на сервере, включая скрытые.