2025-06-11：两个字符串的切换距离。用go语言，给定两个长度相同的字符串 s 和 t，以及两个整数数组 nextCost

2025-06-11：两个字符串的切换距离。用go语言，给定两个长度相同的字符串 s 和 t，以及两个整数数组 nextCost 和 previousCost。我们需要通过一系列操作将 s 转换为 t，每次操作可以选择以下两种方式之一：

1.下一个字母操作：将字符 s[i] 变为字母表中的下一个字母（'z' 变为 'a'），代价为 nextCost[j]，其中 j 是当前字符在字母表中的位置（'a'=0，'b'=1，...，'z'=25）；

2.上一个字母操作：将字符 s[i] 变为字母表中的上一个字母（'a' 变为 'z'），代价为 previousCost[j]，其中 j 同上。

要求计算将 s 转换为 t 所需的最小总代价。

1 <= s.length == t.length <= 100000。

s 和 t 都只包含小写英文字母。

nextCost.length == previousCost.length == 26。

0 <= nextCost[i], previousCost[i] <= 1000000000。

输入：s = "leet", t = "code", nextCost = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], previousCost = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]。

输出：31。

解释：

选择下标 i = 0 并将 s[0] 向前切换 9 次，总代价为 9 。

选择下标 i = 1 并将 s[1] 向后切换 10 次，总代价为 10 。

选择下标 i = 2 并将 s[2] 向前切换 1 次，总代价为 1 。

选择下标 i = 3 并将 s[3] 向后切换 11 次，总代价为 11。

题目来自力扣3361。

代码大体过程详解

1. 预处理和前缀和数组构造

• • 代码中有两个长度是 sigma*2 + 1 = 26*2 + 1 = 53 的前缀和数组，分别是 nxtSum 和 preSum。
• • 其中，nxtSum 用于计算向后（下一个字母）的代价累计和，preSum 用于计算向前（上一个字母）的代价累计和。
• • 为什么长度是 26*2+1？为了方便处理循环移动（字母绕一圈），将字母表按顺序扩展两遍，方便计算连续区间的代价和，避免模运算复杂性。

具体构造：

• • nxtSum[i+1] = nxtSum[i] + nextCost[i % 26]，累计字母表位置的下一个字母代价。
• • preSum[i+1] = preSum[i] + previousCost[i % 26]，累计字母表位置的上一个字母代价。
• • 这样 nxtSum[k] - nxtSum[j] 是字母表从 j 到 k-1 方向上的代价累加。
• • 同理 preSum[k] - preSum[j] 类似，但计算反方向的代价。

2. 逐字符计算从 s[i] 到 t[i] 的最小代价

遍历每个位置 i：

• • 令 x = s[i] - 'a'，y = t[i] - 'a' —— 两字符对应数字索引。

计算两种操作方向的代价：

• • 向后（顺时针）移动：
  • • 如果 y < x，说明要绕字母表圈一圈才能“向后”从 x 到 y，所以把 y 加上 sigma （26）完成区间求和。
  • • res1 = nxtSum[y] - nxtSum[x] 计算从 x 到 y-1 累计的 nextCost 代价（包含循环）。
• • 向前（逆时针）移动：
  • • 如果 x < y，同样需要绕一圈，给 x 加上 sigma。
  • • res2 = preSum[x+1] - preSum[y+1] 计算从 y+1 到 x 累计的 previousCost 代价。
• • 在这两种代价中选择代价进行累加：
  • • ans += min(res1, res2)

总结过程

• • 利用两倍字母长度的前缀和数组快速计算绕过字母表一圈的连续移动代价（避免循环边界判断）。
• • 对每一对 s[i] 和 t[i]，计算两条可选路径花费（顺时针或逆时针操作）。
• • 选出较小的代价累加。
• • 最后得到将 s 转换为 t 的最小总代价。

复杂度分析

• • sigma = 26 是常数，因为字母固定是 26 个。

时间复杂度

• • 生成 nxtSum 和 preSum 前缀和数组花费时间 O(sigma*2)，即常数级别。
• • 对字符串进行单次遍历，计算每个字符的最小代价，花费时间为 O(n)，其中 n = len(s)。
• • 每个字符的代价计算是常数时间操作，包括索引计算和前缀和差值。

所以总时间复杂度是：O(n)

空间复杂度

• • 使用了两个大小约为 53 （常数）的前缀和数组，nxtSum 和 preSum。
• • 不额外开辟与输入规模相关的数组。

所以总额外空间复杂度是：O(1) // 常数级别，不随 n 变化

总结

因此，这段代码整体设计清晰、高效，非常适合处理长度较长（最多10万）的字符串转换问题。

Go完整代码如下：

.

package main

import (
    "fmt"
)

func shiftDistance(s, t string, nextCost, previousCost []int) (ans int64) {
    const sigma = 
    var nxtSum, preSum [sigma* + ]int64
    for i := ; i < sigma*; i++ {
        nxtSum[i+] = nxtSum[i] + int64(nextCost[i%sigma])
        preSum[i+] = preSum[i] + int64(previousCost[i%sigma])
    }
    for i := range s {
        x := s[i] - 'a'
        y := t[i] - 'a'
        if y < x {
            y += sigma
        }
        res1 := nxtSum[y] - nxtSum[x]
        y = t[i] - 'a'
        if x < y {
            x += sigma
        }
        res2 := preSum[x+] - preSum[y+]
        ans += min(res1, res2)
    }
    return
}

func main() {
    s := "leet"
    t := "code"
    nextCost := []int{, , , , , , , , , , , , , , , , , , , , , , , , , }
    previousCost := []int{, , , , , , , , , , , , , , , , , , , , , , , , , }
    fmt.Println(shiftDistance(s, t, nextCost, previousCost))
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def shift_distance(s: str, t: str, next_cost: list, previous_cost: list) -> int:
    sigma = 
    nxt_sum = [] * (sigma *  + )
    pre_sum = [] * (sigma *  + )
    
    for i in range(sigma * ):
        nxt_sum[i+] = nxt_sum[i] + next_cost[i % sigma]
        pre_sum[i+] = pre_sum[i] + previous_cost[i % sigma]
    
    ans = 
    for x_char, y_char in zip(s, t):
        x = ord(x_char) - ord('a')
        y = ord(y_char) - ord('a')
        
        # Calculate next shift cost
        if y < x:
            y += sigma
        res1 = nxt_sum[y] - nxt_sum[x]
        
        # Calculate previous shift cost
        y = ord(y_char) - ord('a')  # reset y
        x = ord(x_char) - ord('a')  # reset x
        if x < y:
            x += sigma
        res2 = pre_sum[x+] - pre_sum[y+]
        
        ans += min(res1, res2)
    
    return ans

def main():
    s = "leet"
    t = "code"
    next_cost = [] * 
    previous_cost = [] * 
    print(shift_distance(s, t, next_cost, previous_cost))

if __name__ == "__main__":
    main()