SWE · Coding

统一循环位移字符串分组:以首字符为基准归一化

每个字符同时在a..z上循环移动相同偏移,才属于同组。

题目重点:每个字符同时在a..z上循环移动相同偏移,才属于同组。

题意与假设

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

  • 只接受ASCII小写a..z,整体统一mod26位移,不能分别调整每个字符。
  • 空串单独成组;组与组内保持首次出现顺序,重复字符串保留。

解题路线

  1. 每个字符串生成key=((ord(c)−ord(first)) mod26)。整体加同一偏移会在相减时抵消。
  2. 反过来key相同,则逐位差都等于首字符的差,因此确实存在同一个循环偏移;这是充要条件。
  3. 长度隐含在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,应先给明确字母表及顺序。
  • 只比较首尾差不足以保证中间所有位置匹配。

继续深挖

  • 支持任意明确字母表时怎样建立字符→序号映射?
  • 若允许旋转字符位置并统一移位,签名及复杂度如何改变?
✓已复制微信号!