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

题目:

视频游戏“辐射4”中，任务“通向*”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

示例：

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

提示：

• ring 和 key 的字符串长度取值范围均为 1 至 100；
• 两个字符串中都只有小写字符，并且均可能存在重复字符；
• 字符串 key 一定可以由字符串 ring 旋转拼出。

抛砖引玉

思路：

整理下题意：

• 指针index在ring字符串的索引0位置，index在ring中允许顺时针逆时针切换(首尾可连贯切换)，切换一次计步数1
• 当指针所对应的元素在key中，拷贝元素计步数1
• 返回切换指针拼凑key的最小步数

1. key中一个字符key[i]到另外一个字符key[i+1]的步数取决于ring中两个字符间的距离，设其为dp[i]

2. 如果ring中没有重复元素，则每个dp[i]最小，最后得到的dp[key.length -1]也一定是最小的，

   但是题目没有限制ring中没有重复元素，就会存在其中一些dp[x]不是最小但是最后组合却最小的情况。

   那么还需要记录每次更新指针后到的不同ring索引的步数，则dp[i][j]表示指针到达key的i索引、ring的j索引所需要的步数

• 记录ring中每个字符所在索引的集合用于计算步数
• 计算key切换指针所需步数：
  key对着字符在ring中的索引j，要到达ring中索引k
  • 顺时针：|j-k|
  • 逆时针：n-|j-k|

/**
 * @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));
};

博客: 前端小书童

每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言

公众号：前端小书童