#514. Freedom Trail

#leetcode

https://leetcode.com/problems/freedom-trail/description/?envType=daily-question&envId=2024-04-27


function findRotateSteps(ring, key) {
    const n = ring.length;
    const m = key.length;
    const memo = new Array(m).fill(0).map(() => new Array(n).fill(0));

    function dp(indexRing, indexKey) {
        if (indexKey === m) return 0;
        if (memo[indexKey][indexRing] !== 0) return memo[indexKey][indexRing];

        let minSteps = Infinity;
        for (let i = 0; i < n; i++) {
            if (ring[i] === key[indexKey]) {
                const clockWise = Math.abs(indexRing - i);
                const counterClockWise = n - clockWise;
                const steps = 1 + Math.min(clockWise, counterClockWise) + dp(i, indexKey + 1);
                minSteps = Math.min(minSteps, steps);
            }
        }

        memo[indexKey][indexRing] = minSteps;
        return minSteps;
    }

    return dp(0, 0);
}