leetcode-No.3146. 两个字符串的排列差

题目

给你两个字符串 s 和 t，每个字符串中的字符都不重复，且 t 是 s 的一个排列。

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

返回 s 和 t 之间的 排列差 。

示例 1：

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

输出：2

解释：

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

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

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

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

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

示例 2：

输入：s = "abcde", t = "edbac"

输出：12

解释： s 和 t 的排列差等于 |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12。

提示：

• 1 <= s.length <= 26

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

• t 是 s 的一个排列。

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

答案代码

"""
给你两个字符串 s 和 t，每个字符串中的字符都不重复，且 t 是 s 的一个排列。
排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。
返回 s 和 t 之间的 排列差 。

示例 1：
输入：s = "abc", t = "bac"
输出：2
解释：
对于 s = "abc" 和 t = "bac"，排列差是：
"a" 在 s 中的位置与在 t 中的位置之差的绝对值。
"b" 在 s 中的位置与在 t 中的位置之差的绝对值。
"c" 在 s 中的位置与在 t 中的位置之差的绝对值。
即，s 和 t 的排列差等于 |0 - 1| + |2 - 2| + |1 - 0| = 2。

示例 2：
输入：s = "abcde", t = "edbac"
输出：12
解释： s 和 t 的排列差等于 |0 - 3| + |1 - 2| + |2 - 4| + |3 - 1| + |4 - 0| = 12。

提示：
1 <= s.length <= 26
每个字符在 s 中最多出现一次。
t 是 s 的一个排列。
s 仅由小写英文字母组成。
"""


class Solution(object):
    """
    该类提供了一个静态方法来计算两个字符串排列之间的差异。
    """

    @staticmethod
    def findPermutationDifference(s, t):
        """
        计算字符串s和t之间的排列差异。

        :type s: str
        :type t: str
        :rtype: int
        """
        # 初始化差异值为0
        diff = 0

        # 创建字典来存储 t 中每个字符的位置
        index_map_t = {char: idx for idx, char in enumerate(t)}

        # 遍历字符串 s
        for idx_s, char_s in enumerate(s):
            if char_s in index_map_t:
                # 如果字符存在于 t 中，则计算其位置差的绝对值
                idx_t = index_map_t[char_s]
                diff += abs(idx_s - idx_t)

        return diff


# 示例代码执行
if __name__ == '__main__':
    s = "abc"
    t = "bac"
    print(Solution.findPermutationDifference(s, t))  # 输出：2
    s = "abcde"
    t = "edbac"
    print(Solution.findPermutationDifference(s, t))  # 输出：12

总结分析

时间复杂度分析

创建字典 index_map_t:

这一步遍历字符串 t，将每个字符及其索引存入字典中。

复杂度为 O(n)，其中 (n) 是字符串 t 的长度。

遍历字符串 s 并计算排列差:

对于字符串 s 中的每个字符，查找它在 t 中的位置，并计算位置差。

复杂度同样为 O(n)，其中 (n) 是字符串 s 的长度。

由于题目假设 s 和 t 的长度相同，因此总的时间复杂度为 O(n)。

空间复杂度分析

字典 index_map_t 的大小取决于字符串 t 的长度，最坏情况下为 O(n)。

变量 diff 为常数空间。

因此，总的空间复杂度为 O(n)。

综上所述：

时间复杂度: (O(n))

空间复杂度: (O(n))

其中 (n) 代表字符串 s 或 t 的长度。

知识点总结

index_map_t = {char: idx for idx, char in enumerate(t)}

1. enumerate(t)：

   enumerate是Python的一个内置函数，它接受一个可迭代对象（比如一个字符串）并返回一个枚举对象。这个枚举对象在每次迭代时会产生一个包含索引和对应元素的元组。

   举个例子，假设t是字符串t = "cab"，那么enumerate(t)会生成：

   [(0, 'c'), (1, 'a'), (2, 'b')]

2. for idx, char in enumerate(t)：

   这部分代码是一个for循环，它遍历enumerate(t)生成的元组。对于t = "cab"，每次循环的idx是字符的索引，char是对应的字符。

   循环的取值依次是：

   • 第一次循环：idx=0, char='c'

   • 第二次循环：idx=1, char='a'

   • 第三次循环：idx=2, char='b'

3. {char: idx for idx, char in enumerate(t)}：

   这是一个字典推导式，用于创建并初始化一个字典。它的格式类似于列表推导式，但是会生成一个字典。

   在每次循环中，字典的键值对{char: idx}会被加入到字典中。

   对于t = "cab"，生成的字典是：

   {
       'c': 0,
       'a': 1,
       'b': 2
   }

综上所述

整段代码index_map_t = {char: idx for idx, char in enumerate(t)}的作用是创建一个字典，该字典将t字符串中的每个字符映射到它的索引位置。

举例说明：

假设t = "hello"，那么执行这段代码后，index_map_t的内容是：

{
    'h': 0,
    'e': 1,
    'l': 3,  # 注意：这里的'l'是最后一个'l'的索引
    'o': 4
}

可以看到，对于重复字符'l'，index_map_t只保留了它在t中最后一次出现的位置（索引3）。