XTY's blog

By XTY, 13 years ago, In Russian
Решение сложностью O(length(string) * Z), где Z = 26. Для решения данной задачи, необходимо было знать алгоритм Дэйсктры, а лучше всего Флойда, т. к. Z = 26, то предпроцессинг за O(Z^3) - не сильно усложнит время выполнения нашей программы. Итак, после чтения строк необходимо сравнить длины строк, и если они не равны, то можно смело выводить -1, т.к. существовать не может. Далее во время считывания символом на которые можно производить замены, ставим в соответствие дугу соответствующей длины, ясно что если при чтении используются только маленькие латинские буквы, то количество вершин в нашем графе будет <= 26 (количество маленьких букв в латинице). После того как мы считали наши переходы следует запустить Флойда(алгоритм поиска кратчайшего пути из одной вершины в другую). После того как мы знаем минимальные стоимости наших замен, то смело пробегаем строкам и ищем на какой символов нам выгоднее всего заменить, его стоимость прибавляем к нашему ответу, при этом изменяя содержимое наших строк. Но если же данной замены не существует, то тоже выводим -1 и прекращаем выполнение нашей программы. Вот в принципе и все.
  • Vote: I like it
  • -9
  • Vote: I do not like it