2186 使两字符串互为字母异位词的最少步骤数

方法一：哈希 + 成员判断【集合】

分别对两个字符串做词频统计，若字符在任意一个字符串出现，则累加其词频，如果同时在两个字符串中出现，则累加其差值。

Python版本

C++版本

复杂度分析

• 时间复杂度：O(N)。 性能开销主要集中在遍历 s 串 和 t 串统计词频中，最坏情况为两个串的长度之和 2 * 2 * 10 ^ 5， 两次遍历词频数组，累计复杂度为52，总复杂度为O(N)。

• 空间复杂度：O(C)。额外占用两个哈希数组，英文小写字母26个，合计52的复杂度。

方法二：字符数组 + 成员判断

用字符数组，即下标为字母的 ASCⅡ码，值为词频统计两个字符串，遍历26个字母，分别统计只在一个字符串的词频，累加其词频，统计同时在两个字符串的字母的词频，累加其差值；

Python版本

C++版本

复杂度分析

• 时间复杂度：O(N)。 性能开销主要集中在遍历 s 串 和 t 串统计词频中，最坏情况为两个串的长度之和 2 * 2 * 10 ^ 5， 一次遍历词频数组，累计复杂度为26，总复杂度为O(N)。

• 空间复杂度：O(C)。额外占用两个哈希数组，英文小写字母26个，合计52的复杂度。

备注

1. 方法二的优点在于快速判断集合关系，不需要使用函数做成员判断，且只需要一层形式上的for循环。

2. 对于哈希数组，判断一个哈希表的键是否在另一个哈希表的键的集合中，C++可以使用 main.find(other)==main.end()。