3361 两个字符串的切换距离

题目描述#

给你两个长度相同的字符串 s 和 t，以及两个整数数组 nextCost 和 previousCost。

一次操作中，你可以选择 s 中的一个下标 i，执行以下操作之一：

将 s[i] 切换为字母表中的下一个字母，如果 s[i] == 'z' ，切换后得到 'a' 。操作的代价为 nextCost[j] ，其中 j 表示 s[i] 在字母表中的下标。
将 s[i] 切换为字母表中的上一个字母，如果 s[i] == 'a' ，切换后得到 'z' 。操作的代价为 previousCost[j] ，其中 j 是 s[i] 在字母表中的下标。

切换距离指的是将字符串 s 变为字符串 t 的最少操作代价总和。

请你返回从 s 到 t 的切换距离。

知识边界#

这道题的核心是将每一位字符的变换代价独立计算，再把所有位置的最小代价累加起来。涉及到的关键知识点有：

1. 字符转下标#

由于只涉及 'a' 到 'z'，可以将字符映射到 0 到 25：

x := s[i] - 'a'
y := t[i] - 'a'

这样就把字符问题转成了环形数组上的位置问题。

2. 环形字母表#

字母表是一个长度为 26 的环：

向后切换：a -> b -> ... -> z -> a
向前切换：a -> z -> ... -> b -> a

所以从一个字符变到另一个字符，有两种方式：

一直向后走
一直向前走

分别计算两种代价，取最小值即可。

3. 前缀和#

为了快速求某一段连续区间的代价和，可以使用前缀和。

设：

preNextCost[i] 表示前 i 个向后切换代价之和
preCost[i] 表示前 i 个向前切换代价之和

那么区间和可以通过两次前缀和相减得到，避免逐步模拟每一次切换。

4. 环形展开成两倍长度#

因为字母表是环，如果直接处理会遇到跨越 'z' -> 'a' 或 'a' -> 'z' 的情况。常见做法是把长度为 26 的代价数组复制一遍，构造长度为 52 的前缀和数组。

例如：

for i := 0; i < sig*2; i++ {
	preNextCost[i+1] = preNextCost[i] + int64(nextCost[i%sig])
	preCost[i+1] = preCost[i] + int64(previousCost[i%sig])
}

这样本来的环形区间，就可以在线性数组中直接求和。

5. Go 中的整数类型#

答案可能很大，因此要使用 int64 保存前缀和与最终答案：

ans := int64(0)

否则可能发生整数溢出。

6. 常见错误点#

向后和向前区间的边界容易写错。
忘记处理环，导致跨越字母表首尾时计算错误。
前缀和数组下标偏移一位时容易出错，尤其是向前切换时的区间定义。

思路#

对于每个位置 i，设：

x = s[i] - 'a'
y = t[i] - 'a'

分别计算：

从 x 向后切换到 y 的总代价
从 x 向前切换到 y 的总代价

然后取两者最小值加入答案。

思路一#

先构造两个长度为 2 * 26 + 1 的前缀和数组：

preNextCost：表示向后切换代价的前缀和
preCost：表示向前切换代价的前缀和

由于字母表是环，所以将两个代价数组都复制一遍，方便处理跨越首尾的情况。

对于某一位字符：

1. 计算向后跳转代价#

如果目标字符 y 在当前字符 x 前面，说明需要绕环走一圈，此时令 y += 26。

这样向后区间就是 [x, y-1]，总代价为：

resBack := preNextCost[y] - preNextCost[x]

2. 计算向前跳转代价#

重新恢复 x 和 y。

如果当前字符 x 在目标字符 y 前面，说明向前走时要绕环一圈，此时令 x += 26。

这样向前区间是 [y+1, x]，总代价为：

resFront := preCost[x+1] - preCost[y+1]

3. 取最小值#

这一位的最优代价就是：

min(resFront, resBack)

把每一位的最小值累加起来就是答案。

思路二#

从本质上看，这题利用了两个关键性质：

每个位置之间互不影响，可以独立求最优解。
每个位置只需要比较“纯向后走”和“纯向前走”两种方案，因为任何来回折返的方案都不会更优。

所以整题可以转化为：

对每一位计算两个方向的区间和
取较小值
累加答案

这样就把原本可能需要逐步模拟的过程，优化成了前缀和查询。

正确性分析#

对于任意位置 i：

从 s[i] 变到 t[i]，只能通过不断向后切换或向前切换完成。
在环形字母表中，从起点到终点的最短候选路径只可能是“全程向后”或“全程向前”。
因为每一步的代价只与当前位置字符有关，路径总代价就是经过边的权重和。
任意混合方向的走法都会产生额外绕路，不可能优于纯向前或纯向后。

因此，对每一位取：

向后总代价
向前总代价

中的较小者，就是该位最小代价。

又因为不同位置之间完全独立，所以总答案就是所有位置最小代价之和。

时间复杂度#

构造前缀和的复杂度是 O(26)，遍历字符串的复杂度是 O(n)，所以总时间复杂度为：

O(n)

空间复杂度#

使用了两个长度为 53 的前缀和数组，空间复杂度为：

O(1)

代码#

func shiftDistance(s string, t string, nextCost []int, previousCost []int) int64 {
	const sig = 26
	preNextCost := make([]int64, 2*sig+1)
	preCost := make([]int64, 2*sig+1)
	for i := 0; i < sig*2; i++ {
		preNextCost[i+1] = preNextCost[i] + int64(nextCost[i%sig])
		preCost[i+1] = preCost[i] + int64(previousCost[i%sig])
	}
	ans := int64(0)
	for i := range s {
		x := s[i] - 'a'
		y := t[i] - 'a'
		// 向后跳转, [x,y-1]
		if y < x {
			y += sig
		}
		resBack := preNextCost[y] - preNextCost[x]
		x = s[i] - 'a'
		y = t[i] - 'a'
		// 向前跳转,[y+1,x]
		if x < y {
			x += sig
		}
		resFront := preCost[x+1] - preCost[y+1]
		ans += min(resFront, resBack)
	}
	return ans
}