Valid Anagram
如果一个字符串是另一个字符串重新排列后的结果，并且它们包含相同的字母，且每个字母出现的次数相同，那么这两个字符串就是字母异位词。给你两个由小写英文字母组成的字符串 s 和 t。如果 t 是 s 的字母异位词，则返回 true，否则返回 false。
函数
- sstring
- 第一个字符串，小写字母
- tstring
- 要与 s 进行测试的字符串
- 返回值boolean
- 当 t 中的字母与 s 中完全相同，且每个字母出现的次数也相同时，结果为 true
约束条件
1 ≤ s.length, t.length ≤ 2 × 104s和t只包含小写英文字母（a到z）。- 这两个长度可能不同。
示例
- 输入
- s = "listen"t = "silent"
- 输出
- true
- 解释
- 这两个单词都包含一个
e、一个i、一个l、一个n、一个s和一个t，所以silent就是字母顺序打乱后的listen。
- 输入
- s = "aabb"t = "abbb"
- 输出
- false
- 解释
- 长度相同，而且都只使用
a和b，但aabb有两个a，而abbb有一个，所以数量不同。
- 输入
- s = "cat"t = "cast"
- 输出
- false
- 解释
cast有 4 个字母，cat有 3 个，所以无论怎样重新排列cat，都无法拼出它。
进阶
如果字符串可以包含任意 Unicode 字符，而不只是从 a 到 z，你会如何修改计数方式？
提示
逐个打开提示，每个都会多透露一点。
字母异位词不考虑字母的顺序。你可以比较什么，既忽略顺序，又保留每个字母出现的次数？
逐个字母排序后，两个变位词会变成相同的字符串。还有更快的方法：字母只有 26 个，因此你可以统计每个字母出现的次数。
如果长度不同，答案就是
false。否则，保留 26 个计数器：s中的每个字母都加 1，t中的每个字母都减 1。当计数器始终没有低于 0 时，这两个字符串恰好互为字母异位词。
题解
字母异位词保留每个字母的数量，但不保留字母的顺序。因此，你需要为每个字符串生成一个摘要，不记录字母的位置，只记录每种字母的数量。排序需要 O(n log n) 的时间来生成摘要；使用包含 26 个计数器的表，只需遍历一遍。
对两个字符串进行排序
思路
排序会将字符串中的字母按字母顺序排列，并抹去每个字母原来的位置。listen 和 silent 排序后都是 eilnst；aabb 和 abbb 排序后仍然不变，并且在索引 1 处不同。两个字符串包含完全相同数量的相同字母，当且仅当它们排序后的形式相等。
先比较长度，如果长度不同，就跳过两次排序。排序需要 O(n log n) 时间，并且在大多数语言中，需要 O(n) 空间来存放字符副本。当 n = 2 × 10^4 时，这种方法很快，但计数所做的工作更少。
算法
- 如果
s和t的长度不同，返回false。 - 将每个字符串中的字符复制到数组中。
- 对两个数组进行排序。
- 如果排序后的数组逐个元素相等，则返回
true。
def isAnagram(s, t):
if len(s) != len(t):
return False
return sorted(s) == sorted(t)统计每个字母
思路
这里只会出现 26 个字母，因此在长度为 26 的数组中为每个字母设置一个计数器，索引为字符编码减去 a 的编码。遍历 s，将每个字母对应的计数器加 1，然后遍历 t，将计数器减 1。
计数器小于 0，说明 t 中该字母的出现次数比 s 多，因此可以立即停止。对于 aabb 和 abbb，遍历完 s 后，计数器显示 a：2，b：2；遍历 t 时，第三个 b 会让 b 的计数器变成 -1，此时返回 false。
如果没有计数器变成负数，说明字母出现次数相同。两个字符串长度相等，因此遍历完后，所有计数器之和为 0；如果没有负数，就不可能有正数与之抵消，所以所有计数器都为 0。这就是为什么长度检查是证明的一部分，而不是捷径。
每个字符串只读取一次，时间复杂度为 O(n)；无论字符串多长，数组都只存放 26 个数字，因此额外空间复杂度为 O(1)。
算法
- 如果
s和t的长度不同，返回false。 - 创建一个包含 26 个 0 的数组。
- 对
s中的每个字母，将对应的计数器加 1。 - 对
t中的每个字母，将对应的计数器减 1；如果计数器小于 0，返回false。 - 返回
true。
def isAnagram(s, t):
if len(s) != len(t):
return False
counts = [0] * 26 # counts[0] is 'a', counts[25] is 'z'
for ch in s:
counts[ord(ch) - ord("a")] += 1
for ch in t:
index = ord(ch) - ord("a")
counts[index] -= 1
if counts[index] < 0:
return False # t uses this letter more often than s
return True
易错点和边界情况
- 比较字母的集合。
aabb和abbb都只包含a和b，但它们并不是字母异位词。 - 检查
t中的每个字母是否都出现在s的某处，却不将其划掉。aab和abb双向检查时都能通过。 - 在计数法中跳过长度检查。对于
s = ab和t = a，没有计数器小于 0，因此代码会错误地返回true。 - 使用原始字符码作为计数器数组的索引。
a的字符码是 97，远超长度为 26 的数组末尾；先减去a的字符码，在 Lua 和 R 中还要加 1，因为它们的数组从 1 开始。
常见问题3
有效字母异位词的时间复杂度是多少？
统计字母需要 O(n) 时间和 O(1) 额外空间，因为无论字符串有多长，计数器数组都只有 26 个元素。对两个字符串排序需要 O(n log n) 时间，排序后的副本通常需要 O(n) 空间。
检查变位词时，排序和计数哪种方法更好？
从理论上看，计数法更快，复杂度为 O(n)，而排序法为 O(n log n)，并且一旦某个字母出现次数过多，就可以立即停止。排序法写起来更简短，而且无需修改就能适用于任何字母表。在面试中，先提到排序法，然后再将其改进为计数法。
为什么使用一个计数器数组，而不是两个？
也可以使用两个数组，每个字符串对应一个：分别统计每个字符串，然后比较这两个数组。使用一个数组，在处理 s 时递增计数，在处理 t 时递减计数，可以节省一半内存；一旦计数器变为负数，就可以立即返回 false，无需最后再进行比较循环。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isAnagram(s, t):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "listen" t = "silent"
预期输出
true