Amazon NG：不用排序签名，按字符计数分组 Anagrams

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练字母表为小写ASCII a-z；空词合法，重复词保留。
• 扩展Unicode须改稀疏字符计数与规范化合同，不能把中文塞26槽。

解题路线

1. 每词扫描一次构造26计数元组作为key，追加到对应组。计数key不可用无分隔拼接，否则不同计数可能编码成同串。
2. 两个词是anagram当且仅当所有字符出现次数相同，完整计数向量恰好表达该充要条件；长度不是单独充分条件。
3. 哈希表可能有hash值碰撞，但语言还比较完整key，碰撞不会把不同向量逻辑上视为相同。不要把单独hash数值当key。
4. 质数乘积在无限精度数学下由唯一分解可区分计数；固定宽度溢出、取模或浮点表示会破坏唯一性。乘积位数还随长度增长，不优于固定字母表计数。

手动走一遍

训练输入["abc","cba","bca","dfadf",""]形成三组，abc组保留三个输入；["ab","aabb"]不能同组。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def group_anagrams(words):
    """Training contract: lowercase ASCII a-z, preserve input order within groups."""
    grouped={}
    for word in words:
        counts=[0]*26
        for ch in word:
            if not 'a' <= ch <= 'z':
                raise ValueError("expected lowercase ASCII")
            counts[ord(ch)-ord('a')]+=1
        grouped.setdefault(tuple(counts),[]).append(word)
    return list(grouped.values())

复杂度

总字符数L、词数n，O(L+26n)期望时间，签名O(26u)加返回引用O(n)；固定26为常数。

易错点与追问

容易失分的边界

• 用字符集合丢失频次。
• 计数直接无分隔字符串拼接。
• 单hash值代替完整签名。

继续深挖

• Unicode和大小写归一化怎样改？
• 如何在外存分组？
• 只返回每组大小能省什么空间？