LeetCode 249. 移位字符串分组

约 4 分钟
文章信息 2 个分类 3 个标签
分类
LeetCode 中等
标签
数组 字符串 哈希表

题目描述

✅ 249. 移位字符串分组

题意分析

对一个小写字母字符串，每次可以把所有字符同时向后移动一位，超过 z 就循环回 a。将能够经过若干次这种整体移动而互相得到的字符串分到同一组。

移位要求所有位置使用同一个偏移量，不能分别改变各字符，也不能交换字符顺序。字符串长度与位置关系都要保留，分组中保存原字符串，重复输入也按各次出现保留。

解法：相对首字符归一化后分组

核心思路

[!blue]

整体移位会改变每个字符的绝对字母值，但不会改变它相对于首字符的循环距离。把每一位减去首字符，再对 26 取模，就得到不受整体平移影响的关系。

用这个关系生成统一签名：把首字符映射成 a，第 i 位映射成 'a' + (s[i] - s[0] + 26) % 26。签名与原串等长，首位固定为 a，其他位置保存相对偏移，因此长度和原有顺序都不会丢失。

两个字符串若能整体移位互相得到，所有位置和首字符增加的是同一偏移，相减后签名必然一致。反过来，若两串签名一致，选择把第一串首字符移到第二串首字符的那个统一偏移，其他各位置也会同时对齐，所以签名相同足以保证属于同组。

哈希表以签名为键，以原字符串列表为值。逐串生成签名并追加到对应组，最后收集所有列表。单字符只有自身相对自身的零偏移，因此自然可以归入同一类；签名只用于分类，不替换结果里的原文。

解题步骤

  1. 创建签名到字符串列表的哈希表。
  2. 对每个字符串，逐位置计算相对首字符的模 26 偏移，再编码为 a..z 的签名字符。
  3. 用完整签名找到或创建分组，将原字符串追加进去。
  4. 处理全部输入后，返回哈希表中的所有分组。

代码实现

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String s : strings) {
            char[] key = new char[s.length()];

            for (int i = 0; i < s.length(); i++) {
                key[i] = (char) ('a' + (s.charAt(i) - s.charAt(0) + 26) % 26);
            }

            groups.computeIfAbsent(new String(key), k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(groups.values());
    }
}

func groupStrings(strings []string) [][]string {
    groups := map[string][]string{}
    for _, s := range strings {
        key := make([]byte, len(s))
        for i := range key {
            key[i] = byte('a' + (int(s[i])-int(s[0])+26)%26)
        }
        k := string(key)
        groups[k] = append(groups[k], s)
    }
    out := make([][]string, 0, len(groups))
    for _, group := range groups {
        out = append(out, group)
    }
    return out
}

复杂度分析

设字符串数量为 N，总字符数为 C。

  • 时间复杂度：期望 $O(N+C)$，每个字符只参与一次签名生成，字符串键的哈希也按字符处理。
  • 空间复杂度：$O(N+C)$，保存各组签名和全部输入项的字符串引用，不复制原字符串内容。

关键点总结

[!green]

  • 相对首字符的循环距离是整体移位的不变量，按位置保存它们就能完整标识类别。
  • 签名相同与可以互相整体移位双向等价，既不会拆散同组，也不会误合并不同组。
  • 长度由签名长度保留，顺序由签名位置保留，不能用字符频次或排序替代。

易错点总结

[!yellow]

  • 差值可能为负，应先加 26 再取模，才能把所有循环距离统一到 0..25。
  • Go 应先把字节转换为 int 再计算有符号差值，与归一化公式保持一致。
  • 对每个字符分别选择不同的偏移，会扩大允许变换的范围，题目只允许统一位移。
  • 把字符串先排序会丢失位置关系，求成另一种分组问题。
  • 将签名放进结果而不是原字符串，会改写用户要求保留的输入内容。

相似题目

题目 难度 关联与区别
49. 字母异位词分组 中等 同样用规范签名分组，但异位词忽略顺序，本题保留顺序并允许整体循环移位。
205. 同构字符串 简单 同样比较字符关系；同构允许任意一一映射，整体移位只允许统一的模 26 偏移。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/55981017
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！