移位字符串分组如何设计归一化 key？（LeetCode 249）

简化版

两个字符串如果每个字符整体平移相同距离后能互相转换，就属于同一组。把每个字符串归一化为“相邻字符差值序列”或“相对首字符偏移序列”作为 key，再用哈希表分组。

详细版

List<List<String>> groupStrings(String[] strings) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strings) {
        String key = buildKey(s);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

String buildKey(String s) {
    StringBuilder key = new StringBuilder();
    for (int i = 1; i < s.length(); i++) {
        int diff = (s.charAt(i) - s.charAt(i - 1) + 26) % 26;
        key.append(diff).append('#');
    }
    return key.toString();
}

例如 "abc" 和 "bcd" 的差值都是 1#1#，"az" 和 "ba" 的差值都是 25#，所以能分到同组。

完整版教学

一、什么叫移位字符串

字符串整体平移是指所有字符都加同一个偏移，并按 26 个小写字母循环。

abc -> bcd -> cde
az  -> ba

这里 "az" 到 "ba" 是合法的，因为 z 再往后是 a。

二、为什么不能直接比较字符

"abc" 和 "bcd" 字符完全不同，但结构一样：相邻字符都差 1。我们要比较的是形状，不是绝对字符。

字符串	相邻差值	分组 key
`abc`	`1,1`	`1#1#`
`bcd`	`1,1`	`1#1#`
`az`	`25`	`25#`
`ba`	`25`	`25#`

相邻差值序列相同，说明整体平移后形状一致。

记忆钩子：移位字符串要比较“形状”，相邻差值就是形状的指纹。

三、循环字母差值怎么计算

普通差值 s[i] - s[i-1] 遇到 "az" 是 25，没问题；遇到 "ba" 是 -1，但循环意义下也应是 25。

所以要写：

int diff = (s.charAt(i) - s.charAt(i - 1) + 26) % 26;

加 26 是为了把负数拉回非负范围。

四、为什么 key 里要加分隔符

如果直接拼数字，差值 [1, 11] 会变成 "111"，差值 [11, 1] 也会变成 "111"，造成假分组。

安全 key: 1#11#
安全 key: 11#1#

分隔符让每个差值边界明确。字符串哈希分组题里，key 的可逆性或无歧义性很重要。

五、另一种归一化方式

也可以把每个字符串平移到以 'a' 开头，记录每个字符相对首字符的偏移：

String normalize(String s) {
    int shift = s.charAt(0) - 'a';
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
        sb.append((char) ('a' + (c - 'a' - shift + 26) % 26));
    }
    return sb.toString();
}

"bcd" 会归一化成 "abc"，"az" 会归一化成 "az"，"ba" 也会归一化成 "az"。

六、复杂度与边界

设总字符数为 S。每个字符只参与一次 key 构造，时间 O(S)；哈希表存储所有字符串，空间 O(S)。

单字符字符串的差值序列为空，都能互相平移，所以应分到同一组。空字符串如果题目允许，也可以把 key 设计成特殊值。

七、常见误区与追问

误区：用排序后的字符作为 key。 移位结构与字母异位词无关，排序会丢失顺序信息。
误区：忘记处理 z -> a 的循环。 差值必须加 26 后取模。
误区：key 不加分隔符。 多位差值会拼接歧义，导致错误分组。
追问：单字符为什么在同一组？ 任意单字符都可通过整体平移变成另一个单字符。
追问：相邻差值和相对首字符哪种更好？ 都可以；相邻差值更短，相对首字符更直观。
追问：复杂度是多少？ 构造 key 扫描总字符数一次，时间 O(S)。

八、加强记忆

移位分组的本质是“去掉绝对起点，只保留形状”。形状可以是相邻差值，也可以是相对首字符。看到循环字母，条件反射写 (x + 26) % 26；看到数字拼 key，条件反射加分隔符。

简化版

详细版