Задача: 514. Freedom Trail
Сложность: hard

В видеоигре Fallout 4 в квесте "Дорога к свободе" игрокам нужно добраться до металлического диска, называемого "Кольцо Свободы", и использовать его для набора определённого ключевого слова, чтобы открыть дверь.
Дана строка ring, представляющая код, выгравированный на внешнем кольце, и другая строка key, представляющая ключевое слово, которое нужно набрать. Верните минимальное количество шагов, чтобы набрать все символы ключевого слова.
Изначально первый символ кольца выровнен в направлении "12 часов". Вы должны набирать все символы из строки key один за другим, поворачивая кольцо по часовой или против часовой стрелки, чтобы каждый символ строки key выровнять в направлении "12 часов", а затем нажимая на центральную кнопку.
На этапе вращения кольца для набора символа key[i]:
Вы можете вращать кольцо по часовой или против часовой стрелки на одно место, что считается одним шагом. Конечная цель вращения — выровнять один из символов кольца в направлении "12 часов", и этот символ должен быть равен key[i].
Если символ key[i] уже выровнен в направлении "12 часов", нажмите центральную кнопку, чтобы набрать его, что также считается одним шагом. После нажатия вы можете начинать набирать следующий символ из key (следующий этап). Иначе, вы завершили весь набор.

Пример:

Input: ring = "godding", key = "godding"
Output: 13

👨‍💻 Алгоритм:

1⃣Определите функцию countSteps для вычисления минимального пути между двумя индексами кольца ring. Создайте переменные ringLen и keyLen для хранения длин кольца и ключа соответственно. Создайте словарь bestSteps для хранения минимального количества шагов для нахождения символа на keyIndex, когда ringIndex кольца выровнен в позиции "12 часов".

2⃣Определите функцию tryLock, которая возвращает минимальное количество шагов для набора ключевого слова. Параметры: ringIndex, keyIndex, minSteps (минимальные шаги для набора ключевого слова на данный момент). Проверьте, равен ли keyIndex значению keyLen; если да, верните 0. Проверьте, есть ли пара (ringIndex, keyIndex) в bestSteps. Если есть, верните bestSteps[ringIndex][keyIndex]. Пройдите по каждому charIndex в ring. Если ring[charIndex] равен key[keyIndex], вычислите totalSteps, добавляя результат countSteps, единицу (нажатие центральной кнопки) и результат tryLock для следующего символа в key. Сохраните минимальное значение между totalSteps и текущим minSteps в minSteps. Сохраните minSteps для (ringIndex, keyIndex) в bestSteps.

3⃣Вызовите tryLock(0, 0, INT_MAX), начиная с нулевого индекса ring в позиции "12 часов" и первого символа в key. Наибольшее целое число передается как последний параметр, так как путь между нулевым индексом ring и первым символом key еще не определен.

😎 Решение:

class Solution {
    findRotateSteps(ring, key) {
        const ringLen = ring.length;
        const keyLen = key.length;
        const bestSteps = new Map();
        
        const countSteps = (curr, next) => {
            const stepsBetween = Math.abs(curr - next);
            const stepsAround = ringLen - stepsBetween;
            return Math.min(stepsBetween, stepsAround);
        }
        
        const tryLock = (ringIndex, keyIndex) => {
            const keyPair = `${ringIndex}-${keyIndex}`;
            if (bestSteps.has(keyPair)) {
                return bestSteps.get(keyPair);
            }
            
            if (keyIndex === keyLen) {
                bestSteps.set(keyPair, 0);
                return 0;
            }
            
            let minSteps = Infinity;
            for (let charIndex = 0; charIndex < ringLen; charIndex++) {
                if (ring[charIndex] === key[keyIndex]) {
                    minSteps = Math.min(minSteps, 
                        countSteps(ringIndex, charIndex) + 1 + tryLock(charIndex, keyIndex + 1));
                }
            }
            bestSteps.set(keyPair, minSteps);
            return minSteps;
        }
        
        return tryLock(0, 0);
    }
}

Ставь 👍 и забирай 📚 Базу знаний