biweekly contest 144。
這鳥題應該只值 4 分,設 5 分真的是抬舉。

題目

輸入兩個相同長度的字串 s 和 t,以及兩個整數陣列 nextCost 和 previousCost。

每次操作,你可以選擇任意 s[i],並執行以下動作之一:

  • 將 s[i] 變成字母表中的下一個字母。若 s[i] == ‘z’,則變成 ‘a’。
    若 s[i] = j,則操作成本為 nextCost[j]。
  • 將 s[i] 變成字母表中的上一個字母。若 s[i] == ‘a’,則變成 ‘z’。
    若 s[i] = j,則操作成本為 previousCost[j]。

移動距離指的是將 s 變成 t 的最小總成本

求 s 變成 t 的移動距離。

解法

要把字元 x 變成 y 只有兩種選擇:

  • 不斷換成前一個字元。
  • 不斷換成後一個字元。

回頭一定是繞遠路,只能固定一個方向走。
一個方向最多走 25 步,而且兩方向加起來至多 26 步。
枚舉兩個方向的成本取最小值即可。

時間複雜度 O(N)。
空間複雜度 O(1)。

class Solution:
    def shiftDistance(self, s: str, t: str, nextCost: List[int], previousCost: List[int]) -> int:

        def f(x, y):
            x, y = ord(x)-97, ord(y)-97
            cost = 0
            while x != y:
                cost += nextCost[x]
                x = (x+1) % 26
            return cost

        def g(x, y):
            x, y = ord(x)-97, ord(y)-97
            cost = 0
            while x != y:
                cost += previousCost[x]
                x = (x-1) % 26
            return cost

        ans = 0
        for x, y in zip(s, t):
            ans += min(f(x, y), g(x, y))

        return ans