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

这道题到底在问什么

输入

s="bab", t="aba"

输出

1

输入

s="leetcode", t="practice"

输出

5

最优解：一步一步想明白

1. 3记住「s 建需求账本 → 扫 t：账本还要就认领、不要就替换」，下面每帧都在套它。
2. 4屏幕上是 t="practice" 的每个字符，待会儿一个个判断它该保留还是替换。
3. 5先统计 s 的需求账本：c×1 d×1 e×3 l×1 o×1 t×1。这就是 t 最终要凑齐的字母清单。
4. 6开始从左到右扫 t。指针指向当前字符，对照账本决定它的命运。
5. 7扫到 t[0]=p。查账本：p 还需要 0 个。不需要了 → 多余。
6. 8p 是多余的（红色），必须替换掉，已替换 1 步。
7. 9扫到 t[1]=r。查账本：r 还需要 0 个。不需要了 → 多余。
8. 10r 是多余的（红色），必须替换掉，已替换 2 步。
9. 11扫到 t[2]=a。查账本：a 还需要 0 个。不需要了 → 多余。
10. 12a 是多余的（红色），必须替换掉，已替换 3 步。
11. 13扫到 t[3]=c。查账本：c 还需要 1 个。还需要 → 可以认领。
12. 14c 被认领（绿色），s 账本里 c 减到 0。这个字符保留、不用改。
13. 15扫到 t[4]=t。查账本：t 还需要 1 个。还需要 → 可以认领。
14. 16t 被认领（绿色），s 账本里 t 减到 0。这个字符保留、不用改。
15. 17扫到 t[5]=i。查账本：i 还需要 0 个。不需要了 → 多余。
16. 18i 是多余的（红色），必须替换掉，已替换 4 步。
17. 19扫到 t[6]=c。查账本：c 还需要 0 个。不需要了 → 多余。
18. 20c 是多余的（红色），必须替换掉，已替换 5 步。
19. 21扫到 t[7]=e。查账本：e 还需要 3 个。还需要 → 可以认领。
20. 22e 被认领（绿色），s 账本里 e 减到 2。这个字符保留、不用改。
21. 23扫完 t：绿色 3 个是能保留的，红色 5 个是多余、必须替换的。所以最少替换 5 步——把这 5 个红字符改成 s 还缺的字母即可。

⚠️ 容易写错的地方

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

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        cnt = [0] * 26
        for ch in s:
            cnt[ord(ch) - 97] += 1
        for ch in t:
            cnt[ord(ch) - 97] -= 1
        return sum(x for x in cnt if x > 0)

#include <string>
#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 x : cnt) if (x > 0) ans += x;
        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 x : cnt) if (x > 0) ans += x;
        return ans;
    }
}

复杂度

面试官可能追问