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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给你两个长度相等的字符串 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 只包含小写英文字母

方法一：两次哈希计数

题目要求制造字母异位词，所以字母的位置不需要考虑，只需要考虑每种字母的数量。使用哈希表对字母进行计数。计数结束后，检查字符串 s 的哪些字母比字符串 t 中的少，那么 s 需要通过变换补齐这些字母来构造 t 的字母异位词。s 需要补的字母的数量即为需要的步数。

[]
1
2
3
4
5
6
7
8
9
class Solution:
    def minSteps(self, s: str, t: str) -> int:
        s_cnt = collections.Counter(s)
        t_cnt = collections.Counter(t)
        ans = 0
        for c in set(s_cnt.keys()).union(set(t_cnt.keys())):
            if s_cnt[c] < t_cnt[c]:
                ans += t_cnt[c] - s_cnt[c]
        return ans
[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minSteps(string s, string t) {
        int s_cnt[26] = {0};
        int t_cnt[26] = {0};
        for (char c : s)
            ++s_cnt[c - 'a'];
        for (char c : t)
            ++t_cnt[c - 'a'];
        int ans = 0;
        for (int i = 0; i != 26; ++i)
            if (s_cnt[i] < t_cnt[i])
                ans += t_cnt[i] - s_cnt[i];
        return ans;
    }
};
复杂度分析：
  • 时间复杂度：O(n)，n 为字符串 s 与 t 的长度之和
    哈希表的查询时间复杂度为 O(1)，查询次数为 O(n)，综合起来，时间复杂度为 O(n)。
  • 空间复杂度：O(1)
    哈希表中存放的元素至多为 26 个，因此内存需求不会随着字符串的变长而增加。

方法二：单次哈希计数

观察方法一，可以发现，两个次数器之间只有求差值的操作。因此，可以将 t 的计数过程直接改为与 s 的计数求差值，而不需要对 t 进行完整的计数。这样做可以进一步减少哈希表的内存消耗。

[]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def minSteps(self, s: str, t: str) -> int:
        s_cnt = collections.Counter(s)
        ans = 0
        for char in t:
            if s_cnt[char] > 0:
                s_cnt[char] -= 1
            else:
                ans += 1
        return ans
[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minSteps(string s, string t) {
        int s_cnt[26] = {0};
        for (char c : s)
            ++s_cnt[c - 'a'];
        int ans = 0;
        for (char c : t)
            if (s_cnt[c - 'a'] == 0)
                ++ans;
            else
                --s_cnt[c - 'a'];
        return ans;
    }
};
复杂度分析：
  • 时间复杂度：O(n)，n 为字符串 s 与 t 的长度之和
    哈希表的查询时间复杂度为 O(1)，查询次数为 O(n)，综合起来，时间复杂度为 O(n)。
  • 空间复杂度：O(1)
    哈希表中存放的元素至多为 26 个，因此内存需求不会随着字符串的变长而增加。
 Comments
On this page
1347-制造字母异位词的最小步骤数