2024-12-20：两个字符串的排列差。用go语言，给定两个字符串 s 和 t，每个字符串中的字符都是唯一的，并且 t 是 s 的一种排列。

我们定义 排列差 为 s 和 t 中每个字符在两个字符串中位置的绝对差值的总和。

请计算并返回 s 和 t 之间的排列差。

1 <= s.length <= 26。

每个字符在 s 中最多出现一次。

t 是 s 的一个排列。

s 仅由小写英文字母组成。

输入：s = "abc", t = "bac"。

输出：2。

解释：

对于 s = "abc" 和 t = "bac"，排列差是：

1."a" 在 s 中的位置与在 t 中的位置之差的绝对值。

2."b" 在 s 中的位置与在 t 中的位置之差的绝对值。

3."c" 在 s 中的位置与在 t 中的位置之差的绝对值。

即，s 和 t 的排列差等于 |0 - 1| + |1 - 0| + |2 - 2| = 2。

答案2024-12-20：

chatgpt[1]

题目来自leetcode3146。

大体步骤如下：

1.创建一个映射char2index，用来记录s字符串中每个字符对应的索引位置。

2.初始化排列差的总和sum为0。

3.遍历字符串t中的每个字符c，计算该字符在t中的索引位置i和在s中对应字符c在s中的索引位置char2index[c]之差的绝对值，加到sum中。

4.返回sum作为s和t之间的排列差。

时间复杂度分析：

• ? 遍历s字符串构建char2index映射的时间复杂度：O(s)，其中s是字符串s的长度。
• ? 遍历t字符串计算排列差总和的时间复杂度：O(t)，其中t是字符串t的长度。

总的时间复杂度：O(s + t)

空间复杂度分析：

• ? 使用一个char2index映射来存储字符到索引位置的映射，空间复杂度为O(26)，因为每个小写字母最多26个。
• ? 使用了常数级额外空间来存储sum和局部变量。

总的额外空间复杂度：O(1)

Go完整代码如下：

package main

import (
    "fmt"
    "math"
)

func findPermutationDifference(s string, t string) int {
    char2index := make(map[rune]int)
    for i, c := range s {
        char2index[c] = i
    }
    sum := 0
    for i, c := range t {
        sum += int(math.Abs(float64(i - char2index[c])))
    }
    return sum
}

func main() {
    s := "abc"
    t := "bac"
    fmt.Println(findPermutationDifference(s, t))
}

Rust完整代码如下：

use std::collections::HashMap;

fn find_permutation_difference(s: &str, t: &str) -> i32 {
    let mut char_to_index: HashMap<char, usize> = HashMap::new();
    
    for (i, c) in s.chars().enumerate() {
        char_to_index.insert(c, i);
    }

    let mut sum = 0;
    
    for (i, c) in t.chars().enumerate() {
        if let Some(&index) = char_to_index.get(&c) {
            sum += (i as i32 - index as i32).abs();
        }
    }

    sum
}

fn main() {
    let s = "abc";
    let t = "bac";
    println!("{}", find_permutation_difference(s, t));
}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP