leetcode
leetcode 1901 ~ 1950
制造字母异位词的最小步骤数 II

制造字母异位词的最小步骤数 II

难度:

标签:

题目描述

代码结果

运行时间: 166 ms, 内存: 17.3 MB


// Java Stream solution to find the minimum steps to make two strings anagrams
// by appending characters to either string

import java.util.stream.*;

public class AnagramStepsStream {
    public int minSteps(String s, String t) {
        // Create frequency arrays for both strings
        int[] sFreq = new int[26];
        int[] tFreq = new int[26];
        
        // Populate frequency arrays using Streams
        s.chars().forEach(c -> sFreq[c - 'a']++);
        t.chars().forEach(c -> tFreq[c - 'a']++);
        
        // Calculate the total number of steps needed using Streams
        return IntStream.range(0, 26)
                         .map(i -> Math.abs(sFreq[i] - tFreq[i]))
                         .sum();
    }
    
    public static void main(String[] args) {
        AnagramStepsStream solution = new AnagramStepsStream();
        String s = "leetcode";
        String t = "coats";
        System.out.println(solution.minSteps(s, t)); // Output: 7
    }
}

解释

方法:

本题解采用计数字典来记录两个字符串中每个字符的出现次数。首先,使用Counter对字符串s和t进行计数获取cnt1和cnt2。然后,通过将cnt1和cnt2相加,得到一个新的计数字典cnt,其中的值是字符在s和t中出现的总次数。接着,遍历cnt字典的每个键值对,计算每个字符在s中应有的数量(即总数的一半,这样才能使s和t的该字符数量相等),通过累加每个字符的差的绝对值来计算需要添加的字符总数。

时间复杂度:

O(n + m)

空间复杂度:

O(u)

代码细节讲解

🦆
题解中提到了使用Counter来计数s和t中的每个字符,为什么选择Counter而不是其他数据结构?
Counter 是 Python collections 模块中的一个特殊的字典类,专门用于计数可哈希对象。它提供了直观的函数和操作来计数元素的频率,如自动计数和合并计数。使用 Counter 可以简化代码,并且比手动使用普通字典更高效,因为它内部优化了计数逻辑。此外,Counter 支持直接的数学运算,如加法和减法,这在处理两个字符串中字符的总出现次数时非常有用。因此,选择 Counter 是因为它的便捷性和对问题场景的直接支持。
🦆
在计算`ans += abs(v - 2 * cnt1[k])`时,这里的计算逻辑是如何确保s和t互为字母异位词的?
此计算公式基于使两个字符串 s 和 t 的每个字符数量相等的目标。变量 `v` 代表字符 k 在 s 和 t 中总共出现的次数,而 `2 * cnt1[k]` 是字符 k 在 s 中应出现的两倍计数。这个差的绝对值 `abs(v - 2 * cnt1[k])` 表示 s 需要增加或减少多少个字符 k 来使其数量达到总数的一半,从而与 t 中的数量相匹配。这确保了在最终的 s 和 t 中,每个字符的数量是相等的,满足字母异位词的条件。
🦆
为什么需要将cnt1和cnt2的计数结果相加,这样做有什么具体的目的或优势?
将 cnt1 和 cnt2 相加的目的是得到一个包含所有字符的总计数,这简化了比较和计算过程。通过这种方式,我们可以直接计算出每个字符应在两个字符串中平均出现的次数(即总数的一半)。这使得可以一步计算出两个字符串中每个字符的目标数量,进而直接计算出需要添加或减少的字符数量。总的来说,这种方法提高了效率和代码的清晰度,避免了繁琐的单独处理每个字符串的步骤。

相关问题