LeetCode 题解工作台
两个字符串的排列差
给你两个字符串 s 和 t ，每个字符串中的字符都不重复，且 t 是 s 的一个排列。 排列差 定义为 s 和 t 中每个字符在两个字符串中位置的绝对差值之和。 返回 s 和 t 之间的 排列差 。 示例 1： 输入： s = "abc", t = "bac" 输出： 2 解释： 对于 s = "a…
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 哈希·表·结合·string
答案摘要
我们可以使用哈希表或者一个长度为 的数组 来存储字符串 中每个字符的位置。 然后遍历字符串 ，计算每个字符在字符串 中的位置与在字符串 中的位置之差的绝对值之和即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
给你两个字符串 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| + |1 - 0| + |2 - 2| = 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:
def findPermutationDifference(self, s: str, t: str) -> int:
d = {c: i for i, c in enumerate(s)}
return sum(abs(d[c] - i) for i, c in enumerate(t))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for building the hash table and iterating through t, where n is the length of the strings. Space complexity is O(n) to store character-to-index mappings. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidates immediately use a mapping to avoid nested loops.
- question_mark
Listen for mentions of absolute differences and character positions.
- question_mark
Observe whether they consider constraints like single occurrence of characters.
常见陷阱
外企场景- error
Using nested loops to search indices instead of a hash table, causing O(n^2) time.
- error
Forgetting that t is always a permutation of s, leading to unnecessary checks.
- error
Incorrectly summing differences without taking absolute values.
进阶变体
外企场景- arrow_right_alt
Allow characters to repeat and calculate permutation difference accordingly.
- arrow_right_alt
Return an array of individual differences for each character instead of the sum.
- arrow_right_alt
Compute permutation difference for multiple pairs of strings in batch efficiently.