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 mainimport ( "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