Medium

题目描述

给你两个字符串 s 和 t。在一步操作中，你可以给 s 或者 t 追加任何字符。

返回使 s 和 t 互为字母异位词的最少步骤数。

字符串的字母异位词是包含相同字符但顺序不同（或相同）的字符串。

示例 1：

输入：s = "leetcode", t = "coats"
输出：7
解释：
- 用 2 步操作，我们可以将 "as" 追加到 s = "leetcode" 中，得到 s = "leetcodeas"。
- 用 5 步操作，我们可以将 "leede" 追加到 t = "coats" 中，得到 t = "coatsleede"。
"leetcodeas" 和 "coatsleede" 现在是字母异位词。
我们总共用了 2 + 5 = 7 步。
可以证明无法用少于 7 步操作使它们互为字母异位词。

示例 2：

输入：s = "night", t = "thing"
输出：0
解释：给定的字符串已经互为字母异位词。因此，我们不需要任何进一步的操作。

提示：

  • 1 <= s.length, t.length <= 2 * 10^5
  • s 和 t 由小写英文字母组成

解题思路

要使两个字符串成为字母异位词，需要让它们包含相同的字符，每个字符的出现次数也要相同。

核心思路：

  1. 字母异位词的关键是字符频次相同，顺序无关
  2. 统计两个字符串中每个字符的频次
  3. 对于每个字符，计算两字符串中该字符频次的差值绝对值
  4. 这个差值就是需要添加的字符数量

算法步骤：

  1. 使用哈希表或数组统计字符串 s 和 t 中每个字符的出现频次
  2. 遍历所有可能的字符（a-z），计算每个字符在两个字符串中频次的差值绝对值
  3. 将所有差值累加即为答案

举例说明：

  • 对于 s = "leetcode", t = "coats"
  • 统计频次：s中 l:1, e:3, t:1, c:1, o:1, d:1；t中 c:1, o:1, a:1, t:1, s:1
  • 差值：l需要1个，e需要3个，d需要1个，a需要1个，s需要1个
  • 总计：1+3+1+1+1=7步

这种方法时间复杂度为 O(n+m)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> freq(26, 0);
        
        // 统计 s 中字符频次（正数）
        for (char c : s) {
            freq[c - 'a']++;
        }
        
        // 统计 t 中字符频次（负数）
        for (char c : t) {
            freq[c - 'a']--;
        }
        
        // 计算需要添加的字符总数
        int steps = 0;
        for (int f : freq) {
            steps += abs(f);
        }
        
        return steps;
    }
};

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        from collections import Counter
        
        # 统计两个字符串的字符频次
        freq_s = Counter(s)
        freq_t = Counter(t)
        
        # 计算需要添加的字符总数
        steps = 0
        # 获取所有出现的字符
        all_chars = set(freq_s.keys()) | set(freq_t.keys())
        
        for char in all_chars:
            steps += abs(freq_s[char] - freq_t[char])
        
        return steps

public class Solution {
    public int MinSteps(string s, string t) {
        int[] freq = new int[26];
        
        // 统计 s 中字符频次（正数）
        foreach (char c in s) {
            freq[c - 'a']++;
        }
        
        // 统计 t 中字符频次（负数）
        foreach (char c in t) {
            freq[c - 'a']--;
        }
        
        // 计算需要添加的字符总数
        int steps = 0;
        for (int i = 0; i < 26; i++) {
            steps += Math.Abs(freq[i]);
        }
        
        return steps;
    }
}

var minSteps = function(s, t) {
    const freq = new Array(26).fill(0);
    
    // 统计 s 中字符频次（正数）
    for (const char of s) {
        freq[char.charCodeAt(0) - 97]++;
    }
    
    // 统计 t 中字符频次（负数）
    for (const char of t) {
        freq[char.charCodeAt(0) - 97]--;
    }
    
    // 计算需要添加的字符总数
    let steps = 0;
    for (const f of freq) {
        steps += Math.abs(f);
    }
    
    return steps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n + m)
空间复杂度O(1)

其中 n 和 m 分别是字符串 s 和 t 的长度。由于只使用固定大小（26）的数组存储字符频次，空间复杂度为常数级别。

相关题目