LEETCODE 1347. Minimum Number of Steps to Make Two Strings Anagram 解题思路分析

题目大意：

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

给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的 任一字符 替换为 另一个字符。

返回使 t 成为 s 的字母异位词的最小步骤数。

字母异位词 指字母相同，但排列不同的字符串。

示例 1：

输出：s = "bab", t = "aba"
输出：1
提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。

示例 2：

输出：s = "leetcode", t = "practice"
输出：5
提示：用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 变成 s 的字母异位词。

示例 3：

输出：s = "anagram", t = "mangaar"
输出：0
提示："anagram" 和 "mangaar" 本身就是一组字母异位词。 

示例 4：

输出：s = "xxyyzz", t = "xxyyzz"
输出：0

示例 5：

输出：s = "friend", t = "family"
输出：4

提示：

• 1 <= s.length <= 50000
• s.length == t.length
• s 和 t 只包含小写英文字母

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1347

解题思路分析：

读完本题之后第一想法是使用动态规划，不过仔细考虑过后发现这道题并没有那么复杂，如果将一个单词变成另一个单词的异位词，实际上就是要让两个单词的每种字母个数都相同即可。

解题时，我们先建立一个count数组，统计出单词s中每种字母个数，即单词s中有多少个a，多少个b。。。多少个z。然后再遍历单词t的每个字母，将该字母在count数组中出现的次数减去1。遍历完之后，count数组中所有为正数的部分，都是相对于单词s，单词t中不足的部分。我们将这部分的数字累加即是结果。（延伸思考：虽与与本题结果无关，为了更好理解该算法，这里啰嗦一下。count数组中为0的部分代表s和t中该字母出现次数相同，为负数的部分代表t中该字母数量多于s）

实现代码：

public int minSteps(String s, String t) {
    // 统计每种字母出现的次数
    int[] count = new int[26];
    // 为了提高效率，将字符串转为数组
    char[] sarr = s.toCharArray();
    // 循环单词s的每个字符
    for(int i=0;i<sarr.length;i++){
        // 当前字符出现次数加一
        count[sarr[i]-'a']++;
    }
    // 循环t的每个字符
    char[] tarr = t.toCharArray();
    for(int i=0;i<tarr.length;i++){
        // 当前字符出现次数减一
        count[tarr[i]-'a']--;
    }
    // 返回结果
    int res=0;
    // 累加count数组中大于0的部分
    for(int i=0;i<26;i++){
        if(count[i]>0) res+=count[i];
    }
    return res;
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 100.00% of Java online submissions for Minimum Number of Steps to Make Two Strings Anagram.

Memory Usage: 42.1 MB, less than 100.00% of Java online submissions for Minimum Number of Steps to Make Two Strings Anagram.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1347-minimum-number-of-steps-to-make-two-strings-anagram-解题思路分析/