【一天一大 lee】自由之路 (难度:困难) - Day20201111

输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

/**
 * @param {string} ring
 * @param {string} key
 * @return {number}
 */
var findRotateSteps = function(ring, key) {
 let m = key.length,
  n = ring.length,
  map = new Map()
 // 记录ring中每个字符的索引
 for (let i = 0; i < n; i++) {
  if (map.has(ring[i])) {
   map.get(ring[i]).push(i)
  } else {
   map.set(ring[i], [i])
  }
 }
 let dp = Array.from({ length: m }, () => Array(n).fill(Number.MAX_VALUE)),
  // 第一个字符在ring中的索引集合
  indexList = map.get(key.charAt(0));
 // 从ring索引0到达key的第一个字符的步数，顺时针i，逆时针n-i
 indexList.forEach(i => {
  dp[0][i] = Math.min(i, n - i) + 1;
 })
 for (let i = 1; i < m; i++) {
  indexList = map.get(key.charAt(i))
  indexList.forEach(j => {
   // 从key的第i-1个元素到第i个元素所需步数
   map.get(key.charAt(i - 1)).forEach(k => {
    // key的第i-1个元素在ring中指针位置j，顺时针|j-k|，逆时针n-|j-k|
    const perNum = Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1;
    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + perNum);
   })
  })
 }
 // 回到key指针到达m-1的最小集合
 return dp[m - 1].reduce((pre, cur) => Math.min(pre, cur));
};