X

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
  • st 只包含小写英文字母

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: 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-解题思路分析/
Categories: leetcode
kwantong: