Easy

题目描述

给你两个字符串 s 和 t，其中每个字符在 s 中最多出现一次，且 t 是 s 的一个排列。

s 和 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 中的索引的绝对差值
即排列差值等于 |0 - 1| + |1 - 0| + |2 - 2| = 2。

示例 2：

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

提示：

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

提示技巧：

  • 对每个字符，找到它在字符串 s 中的索引，然后找到它在字符串 t 中的索引。

解题思路

这道题的关键在于建立字符与索引的映射关系。我们需要计算每个字符在两个字符串中的位置差值。

解题思路：

  1. 哈希表映射法：首先遍历字符串 s，将每个字符及其索引存储在哈希表中。然后遍历字符串 t，对于每个字符，从哈希表中获取它在 s 中的索引，计算与当前在 t 中索引的绝对差值，累加到结果中。

  2. 双重遍历法：对于每个字符，分别在两个字符串中查找其位置。由于字符串长度较小（最多26个字符），这种方法也是可行的。

推荐使用哈希表映射法，因为它的时间复杂度更优，只需要遍历两次字符串，而不需要嵌套循环查找。

具体步骤：

  • 第一次遍历 s，建立字符到索引的映射
  • 第二次遍历 t，查找每个字符在 s 中的索引，计算差值并累加

由于题目保证每个字符最多出现一次，且 t 是 s 的排列，所以不会有重复或缺失的情况。

代码实现

class Solution {
public:
    int findPermutationDifference(string s, string t) {
        unordered_map<char, int> pos;
        
        // 记录字符串 s 中每个字符的位置
        for (int i = 0; i < s.length(); i++) {
            pos[s[i]] = i;
        }
        
        int result = 0;
        // 遍历字符串 t，计算位置差值
        for (int i = 0; i < t.length(); i++) {
            result += abs(pos[t[i]] - i);
        }
        
        return result;
    }
};

class Solution:
    def findPermutationDifference(self, s: str, t: str) -> int:
        # 记录字符串 s 中每个字符的位置
        pos = {char: i for i, char in enumerate(s)}
        
        result = 0
        # 遍历字符串 t，计算位置差值
        for i, char in enumerate(t):
            result += abs(pos[char] - i)
            
        return result

public class Solution {
    public int FindPermutationDifference(string s, string t) {
        Dictionary<char, int> pos = new Dictionary<char, int>();
        
        // 记录字符串 s 中每个字符的位置
        for (int i = 0; i < s.Length; i++) {
            pos[s[i]] = i;
        }
        
        int result = 0;
        // 遍历字符串 t，计算位置差值
        for (int i = 0; i < t.Length; i++) {
            result += Math.Abs(pos[t[i]] - i);
        }
        
        return result;
    }
}

var findPermutationDifference = function(s, t) {
    const pos = new Map();
    
    // 记录字符串 s 中每个字符的位置
    for (let i = 0; i < s.length; i++) {
        pos.set(s[i], i);
    }
    
    let result = 0;
    // 遍历字符串 t，计算位置差值
    for (let i = 0; i < t.length; i++) {
        result += Math.abs(pos.get(t[i]) - i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串的长度。需要遍历两次字符串，每次都是线性时间
空间复杂度O(n)，需要哈希表存储字符到索引的映射关系

相关题目