题目重点:每个字符同时在a..z上循环移动相同偏移,才属于同组。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 只接受ASCII小写a..z,整体统一mod26位移,不能分别调整每个字符。
- 空串单独成组;组与组内保持首次出现顺序,重复字符串保留。
解题路线
- 每个字符串生成key=((ord(c)−ord(first)) mod26)。整体加同一偏移会在相减时抵消。
- 反过来key相同,则逐位差都等于首字符的差,因此确实存在同一个循环偏移;这是充要条件。
- 长度隐含在tuple长度里。空串key空tuple,单字母key=(0,),因此两类不会混组。
手动走一遍
abc、bcd、xyz都得到(0,1,2),同组;az、ba得到(0,25),另组。a、z同组,因为长度1可统一移动;aa与ab不同,key分别(0,0)与(0,1)。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
def group_shifted(words):
groups = {}
for w in words:
if any(c < 'a' or c > 'z' for c in w):
raise ValueError("lowercase ASCII only")
key = tuple((ord(c) - ord(w[0])) % 26 for c in w) if w else ()
groups.setdefault(key, []).append(w)
return list(groups.values())
复杂度
O(L)期望时间和O(L+n)输出/键空间,L为所有字符串字符数。若把实际内容引用当输入已有,新增键仍需O(L)。
易错点与追问
容易失分的边界
- 大小写混合不能直接假设mod52,应先给明确字母表及顺序。
- 只比较首尾差不足以保证中间所有位置匹配。
继续深挖
- 支持任意明确字母表时怎样建立字符→序号映射?
- 若允许旋转字符位置并统一移位,签名及复杂度如何改变?
