golang 解法, 执行用时: 0 ms, 内存消耗: 3.2 MB, 提交时间: 2023-06-25 14:42:17

func minimumDistance(word string) int {
	if len(word) < 3 {
		return 0
	}
	dp := make([][]int, len(word))
	for i := 0; i < len(word); i++ {
		dp[i] = make([]int, 26)
		for j := 0; j < 26; j++ {
			dp[i][j] = math.MaxInt32 >> 1
		}
	}
	for i := 0; i < 26; i++ {
		dp[0][i] = 0
	}
	var ans = math.MaxInt32
	for i := 1; i < len(word); i++ {
		cur := int(word[i] - 'A')
		prev := int(word[i-1] - 'A')
		d := distance(prev, cur)
		for j := 0; j < 26; j++ {
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + d)
			if prev == j {
				for k := 0; k < 26; k++ {
					d0 := distance(k, cur)
					dp[i][j] = min(dp[i][j], dp[i - 1][k] + d0)

				}
			}
		}
	}
	for i := 0; i < 26; i++ {
		if ans > dp[len(word)-1][i]{
			ans = dp[len(word)-1][i]
		}
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func distance(i, j int) int {
	a, b := [2]int{i / 6, i % 6}, [2]int{j / 6, j % 6}
	return abs(a[0]-b[0]) + abs(a[1]-b[1])
}

javascript 解法, 执行用时: 68 ms, 内存消耗: 41.4 MB, 提交时间: 2023-06-25 14:41:16

/**
 * @param {string} word
 * @return {number}
 */
const minimumDistance = word => {
  const LEN = word.length;
  const dp = new Uint16Array(LEN - 1);
  let sum = 0

  for (let j = 2; j < LEN; ++j) {
    sum += distance(j - 2, j - 1);
    let min = sum;
    for (let i = 0; i < j - 1; ++i) {
      const min2 = dp[i] + distance(i, j);
      dp[i] = dp[i] + distance(j - 1, j);
      if (min2 < min) min = min2;
    }
    dp[j - 1] = min;
  }

  return Math.min(...dp, sum);

  function distance(a, b) {
    const x = word.charCodeAt(a) - 65;
    const y = word.charCodeAt(b) - 65;
    return Math.abs((x % 6) - (y % 6)) + Math.abs(((x / 6) << 0) - ((y / 6) << 0));
  }
};