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

这道题到底在问什么

输入

s="leetcode", t="coats"

输出

7

输入

s="night", t="thing"

输出

0 (已经互为异位词)

最优解：一步一步想明白

1. 3记牢这一句:扫 s 加一、扫 t 减一,最后把每个字母桶的绝对值加起来。桶里是正数代表 s 多、要补给 t,是负数代表 t 多、要补给 s,补齐都得花绝对值那么多步。下面从清空计数表开始一步步走。
2. 4先建一张计数表。两个串合起来只用到 8 种字母,l e t c o d a s,给每种字母一个桶,格子里前面是字母、后面是它当前的计数,一开始全是 0。接下来先扫 s、再扫 t,让这些数字动起来。
3. 5读到 s 的第 0 个字符是 l。找到它的桶,计数加 1,现在桶 l 里是 1。紫色高亮的就是刚刚更新的那个桶。
4. 6读到 s 的第 1 个字符是 e。找到它的桶,计数加 1,现在桶 e 里是 1。紫色高亮的就是刚刚更新的那个桶。
5. 7读到 s 的第 2 个字符是 e。找到它的桶,计数加 1,现在桶 e 里是 2。e 已经是第 2 次出现了,leetcode 里有 3 个 e,这个桶会一路涨到 3。
6. 8读到 s 的第 3 个字符是 t。找到它的桶,计数加 1,现在桶 t 里是 1。紫色高亮的就是刚刚更新的那个桶。
7. 9读到 s 的第 4 个字符是 c。找到它的桶,计数加 1,现在桶 c 里是 1。紫色高亮的就是刚刚更新的那个桶。
8. 10读到 s 的第 5 个字符是 o。找到它的桶,计数加 1,现在桶 o 里是 1。紫色高亮的就是刚刚更新的那个桶。
9. 11读到 s 的第 6 个字符是 d。找到它的桶,计数加 1,现在桶 d 里是 1。紫色高亮的就是刚刚更新的那个桶。
10. 12读到 s 的第 7 个字符是 e。找到它的桶,计数加 1,现在桶 e 里是 3。e 已经是第 3 次出现了,leetcode 里有 3 个 e,这个桶会一路涨到 3。
11. 13读到 t 的第 0 个字符是 c。给它的桶减 1,现在桶 c 里是 0。桶 c 里 s 和 t 各消掉一个,慢慢往配平的方向走。
12. 14读到 t 的第 1 个字符是 o。给它的桶减 1,现在桶 o 里是 0。桶 o 里 s 和 t 各消掉一个,慢慢往配平的方向走。
13. 15读到 t 的第 2 个字符是 a。给它的桶减 1,现在桶 a 里是 -1。注意它变成了负数,说明这个字母 t 比 s 多,记成红色,后面要把它补给 s。
14. 16读到 t 的第 3 个字符是 t。给它的桶减 1,现在桶 t 里是 0。桶 t 里 s 和 t 各消掉一个,慢慢往配平的方向走。
15. 17读到 t 的第 4 个字符是 s。给它的桶减 1,现在桶 s 里是 -1。注意它变成了负数,说明这个字母 t 比 s 多,记成红色,后面要把它补给 s。
16. 18结算字母 l 这个桶,里面是 1。是正数 1,说明 s 多出 1 个 l,要补 1 个到 t,累计步数加到 1,标红。
17. 19结算字母 e 这个桶,里面是 3。是正数 3,说明 s 多出 3 个 e,要补 3 个到 t,累计步数加到 4,标红。
18. 20结算字母 t 这个桶,里面是 0。正好是 0,说明 s 和 t 里这个字母一样多,已经配平,标绿,不用补,累计步数还是 4。
19. 21结算字母 c 这个桶,里面是 0。正好是 0,说明 s 和 t 里这个字母一样多,已经配平,标绿,不用补,累计步数还是 4。
20. 22结算字母 o 这个桶,里面是 0。正好是 0,说明 s 和 t 里这个字母一样多,已经配平,标绿,不用补,累计步数还是 4。
21. 23结算字母 d 这个桶,里面是 1。是正数 1,说明 s 多出 1 个 d,要补 1 个到 t,累计步数加到 5,标红。
22. 24结算字母 a 这个桶,里面是 -1。是负数 -1,说明 t 多出 1 个 a,要补 1 个到 s,累计步数加到 6,标红。
23. 25结算字母 s 这个桶,里面是 -1。是负数 -1,说明 t 多出 1 个 s,要补 1 个到 s,累计步数加到 7,标红。
24. 26八个桶全部结算完。绿色的 t c o 三个字母 s 和 t 里一样多,不花步数;红色的 l 有 1 个多、e 有 3 个多、d 有 1 个多,这 5 个要补到 t,a 和 s 各差 1 个要补到 s。把红色桶的绝对值加起来,1 加 3 加 1 加 1 加 1 等于 7,这就是最少步骤数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minSteps(self, s: str, t: str) -> int:
        cnt = Counter(s)
        for c in t:
            cnt[c] -= 1
        return sum(abs(v) for v in cnt.values())

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> cnt(26);
        for (char& c : s) ++cnt[c - 'a'];
        for (char& c : t) --cnt[c - 'a'];
        int ans = 0;
        for (int& v : cnt) ans += abs(v);
        return ans;
    }
};

import java.util.*;
class Solution {
    public int minSteps(String s, String t) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        for (char c : t.toCharArray()) {
            --cnt[c - 'a'];
        }
        int ans = 0;
        for (int v : cnt) {
            ans += Math.abs(v);
        }
        return ans;
    }
}

复杂度

面试官可能追问