跳转至

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：

输入：s = "abab", t = "baba", nextCost = [100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], previousCost = [1,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

输出：2

解释：

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

示例 2：

输入：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 。

 

提示：

  • 1 <= s.length == t.length <= 105
  • s 和 t 都只包含小写英文字母。
  • nextCost.length == previousCost.length == 26
  • 0 <= nextCost[i], previousCost[i] <= 109

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def shiftDistance(
        self, s: str, t: str, nextCost: List[int], previousCost: List[int]
    ) -> int:
        m = 26
        s1 = [0] * (m << 1 | 1)
        s2 = [0] * (m << 1 | 1)
        for i in range(m << 1):
            s1[i + 1] = s1[i] + nextCost[i % m]
            s2[i + 1] = s2[i] + previousCost[(i + 1) % m]
        ans = 0
        for a, b in zip(s, t):
            x, y = ord(a) - ord("a"), ord(b) - ord("a")
            c1 = s1[y + m if y < x else y] - s1[x]
            c2 = s2[x + m if x < y else x] - s2[y]
            ans += min(c1, c2)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public long shiftDistance(String s, String t, int[] nextCost, int[] previousCost) {
        int m = 26;
        long[] s1 = new long[(m << 1) + 1];
        long[] s2 = new long[(m << 1) + 1];
        for (int i = 0; i < (m << 1); i++) {
            s1[i + 1] = s1[i] + nextCost[i % m];
            s2[i + 1] = s2[i] + previousCost[(i + 1) % m];
        }
        long ans = 0;
        for (int i = 0; i < s.length(); i++) {
            int x = s.charAt(i) - 'a';
            int y = t.charAt(i) - 'a';
            long c1 = s1[y + (y < x ? m : 0)] - s1[x];
            long c2 = s2[x + (x < y ? m : 0)] - s2[y];
            ans += Math.min(c1, c2);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    long long shiftDistance(string s, string t, vector<int>& nextCost, vector<int>& previousCost) {
        int m = 26;
        vector<long long> s1((m << 1) + 1);
        vector<long long> s2((m << 1) + 1);
        for (int i = 0; i < (m << 1); ++i) {
            s1[i + 1] = s1[i] + nextCost[i % m];
            s2[i + 1] = s2[i] + previousCost[(i + 1) % m];
        }

        long long ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            int x = s[i] - 'a';
            int y = t[i] - 'a';
            long long c1 = s1[y + (y < x ? m : 0)] - s1[x];
            long long c2 = s2[x + (x < y ? m : 0)] - s2[y];
            ans += min(c1, c2);
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func shiftDistance(s string, t string, nextCost []int, previousCost []int) (ans int64) {
    m := 26
    s1 := make([]int64, (m<<1)+1)
    s2 := make([]int64, (m<<1)+1)
    for i := 0; i < (m << 1); i++ {
        s1[i+1] = s1[i] + int64(nextCost[i%m])
        s2[i+1] = s2[i] + int64(previousCost[(i+1)%m])
    }
    for i := 0; i < len(s); i++ {
        x := int(s[i] - 'a')
        y := int(t[i] - 'a')
        z := y
        if y < x {
            z += m
        }
        c1 := s1[z] - s1[x]
        z = x
        if x < y {
            z += m
        }
        c2 := s2[z] - s2[y]
        ans += min(c1, c2)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function shiftDistance(s: string, t: string, nextCost: number[], previousCost: number[]): number {
    const m = 26;
    const s1: number[] = Array((m << 1) + 1).fill(0);
    const s2: number[] = Array((m << 1) + 1).fill(0);
    for (let i = 0; i < m << 1; i++) {
        s1[i + 1] = s1[i] + nextCost[i % m];
        s2[i + 1] = s2[i] + previousCost[(i + 1) % m];
    }
    let ans = 0;
    const a = 'a'.charCodeAt(0);
    for (let i = 0; i < s.length; i++) {
        const x = s.charCodeAt(i) - a;
        const y = t.charCodeAt(i) - a;
        const c1 = s1[y + (y < x ? m : 0)] - s1[x];
        const c2 = s2[x + (x < y ? m : 0)] - s2[y];
        ans += Math.min(c1, c2);
    }
    return ans;
}

评论