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

举报
福大大架构师每日一题 发表于 2024/12/20 09:19:12 2024/12/20
【摘要】 2024-12-20:两个字符串的排列差。用go语言,给定两个字符串 s 和 t,每个字符串中的字符都是唯一的,并且 t 是 s 的一种排列。我们定义 排列差 为 s 和 t 中每个字符在两个字符串中位置的绝对差值的总和。请计算并返回 s 和 t 之间的排列差。1 <= s.length <= 26。每个字符在 s 中最多出现一次。t 是 s 的一个排列。s 仅由小写英文字母组成。输入:s ...

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

题目来自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));
}

在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。