【Leetcode Daily】3361两个字符串的切换距离

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给两个字符串，求一个字符串到另一个字符串的切换距离。所谓切换距离就不在此赘述，总之就是每个字符变换到另一个小写字母的数值和。

思路分享

• 前缀和的思路，可以参考 【Leetcode Daily】303区域和检索-数组不可变

• 前缀和负责解决本题快速计算距离，并且通过增加一倍来解决环形的问题，同时注意往前和往后由于初始的 0，处理会有所不同，真的得自己拿例子推才行。

  https://leetcode.cn/problems/shift-distance-between-two-strings/solutions/2998657/qian-zhui-he-on-zuo-fa-pythonjavacgo-by-b4hfx/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def shiftDistance(self, s: str, t: str, nextCost: List[int], previousCost: List[int]) -> int:
        s_next = list(accumulate(nextCost+nextCost, initial=0))
        s_pre = list(accumulate(previousCost+previousCost, initial=0))
        
        ans = 0
        ord_a = ord('a')
        for x, y in zip(s, t):
            x = ord(x) - ord_a
            y = ord(y) - ord_a
            ans += min(s_next[y+26 if y < x else y] - s_next[x], 
                    s_pre[(x+26 if x < y else x)+1] - s_pre[y+1])

        return ans