#514. Freedom Trail

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);
}