source и target и два массива по 26 чисел — forward_cost и backward_cost. Буквы алфавита стоят по кругу: после 'z' снова идёт 'a'.
За одну операцию можно взять любую позицию i в source и:
- сдвинуть букву на одну вперёд по кругу — это стоит forward_cost[j], где j — номер текущей буквы в алфавите ('a' — 0);
- сдвинуть букву на одну назад по кругу — это стоит backward_cost[j] для текущей буквы с номером j.
Верните минимальную суммарную стоимость, за которую source можно превратить в target.source='cat', target='dog', forward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], backward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] → 26
Каждый шаг стоит 1. «c» → «d» — один шаг вперёд; «a» → «o» — 12 шагов назад дешевле 14 вперёд; «t» → «g» — 13 шагов в любую сторону. Итого 1 + 12 + 13 = 26.
source='b', target='a', forward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], backward_cost=[0, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] → 25
Шаг назад с «b» стоит 100, а обойти круг вперёд — 25 шагов по 1. Выгоднее идти вперёд: ответ 25.
source='abc', target='abc', forward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], backward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] → 0
Строки уже совпадают — крутить ничего не нужно, ответ 0.
source.length == target.length ≤ 10⁵source и target состоят из строчных латинских буквforward_cost.length == backward_cost.length == 26forward_cost[i], backward_cost[i] ≤ 10⁹source='cat', target='dog', forward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], backward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
26
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 82 теста на сервере, включая скрытые.