LeetCode 249 解法揭秘：如何把“abc”和“bcd”分到一组？

摘要

你有没有遇到过这种情况：有一堆字符串，看起来只是“平移”了一下，比如 abc -> bcd，或者 az -> ba，虽然字母换了，但它们给人的感觉还是很像。LeetCode 第 249 题就正好考了这个点：把所有属于同一个“移位字符串序列”的东西分成一组。

别看题目挺简单，其实要把这类“差不多但不完全一样”的字符串精准归类，还是有点技术含量的。这篇文章用 Swift 来做这道题，并结合实际开发场景讲讲它能怎么用，还会附上完整可运行的 Demo 和讲解。

描述

我们有一个只包含小写字母的字符串列表，比如：

["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]

我们希望把其中属于同一“移位序列”的字符串分组。比如：

• "abc" -> "bcd" -> "cde"，这类的归一组
• "az" 和 "ba"，虽然乍看没啥关系，但实际上也算同一个“偏移规律”，可以放一起
• "acef" 没有能跟它组队的，就自己一组

最后的输出应该是这样：

[["abc","bcd","xyz"],["az","ba"],["acef"],["a","z"]
]

痛点分析 & 实际应用场景

这个题其实挺有意思，因为它背后解决的是一种非常实际的问题：怎么找出那些“表面不一样、但本质上变化规律相同”的东西。你可能会觉得这玩意平时开发用不着，但我们来看几个真实场景：

1. 防刷系统识别：

在社交平台上，有些用户发骚扰信息时会稍微改一下内容，比如：

"hi there" -> "ij uifsf" -> "jk vjgtg"

其实就是每个字母往后挪了一位、两位、三位…你肉眼一看很像，但程序该怎么识别出来这是一类“伪装”的垃圾信息呢？这道题的逻辑就能用上。

2. 智能输入法候选词推荐：

用户打了个错别字，比如输入 bcd，其实是想输入 abc，那我们能不能把这种偏移关系也识别出来作为候选词推荐？靠的也是类似的偏移计算。

3. 密码安全检测：

用户试图设置一个和之前密码差不多的新密码，比如原来是 abc123，新设置成 bcd123，其实没啥变化。这种逻辑在安全校验里也是经常遇到的。

4. 自然语言处理中的文本聚类：

比如说一个聊天机器人收集到很多用户的意图，但有一类人喜欢换着字母输入（变形词），你就需要判断这是不是同一类话术模式。

说到底，这题就是在考“如何识别相似但又不是完全一样的内容”。

Swift 题解答案

思路其实不复杂，我们可以对每个字符串生成一个“差值序列”当作 key，比如：

• abc 的字符间差值是 [1, 1]
• bcd 也是 [1, 1]
• az 是 [25]

我们把这些差值转换成字符串作为 map 的 key，然后分组就行了。

可运行 Demo 代码

import Foundationfunc groupStrings(_ strings: [String]) -> [[String]] {var groups = [String: [String]]()for str in strings {var key = ""let chars = Array(str)for i in 1..<chars.count {let diff = (Int(chars[i].asciiValue!) - Int(chars[i - 1].asciiValue!) + 26) % 26key += "\(diff),"}groups[key, default: []].append(str)}return Array(groups.values)
}

题解代码分析

我们来拆解一下关键部分：

差值是怎么来的？

举个例子，abc 中：

• 'b' - 'a' = 1
• 'c' - 'b' = 1

差值数组就是 [1, 1]，我们转成 "1,1," 当作 key。只要差值序列一样，说明这个字符串和前面的某个是“移位版本”。

为什么加 +26 再 %26？

因为我们要处理 'z' -> 'a' 这种环绕关系。比如：

let diff = ('a' - 'z' + 26) % 26 // 结果是 1

这样 az 和 ba 这类看似不连贯的字符串，也能算是同一组。

示例测试及结果

来跑个例子看看效果：

let input = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
let result = groupStrings(input)for group in result {print(group)
}

打印结果：

["abc", "bcd", "xyz"]
["az", "ba"]
["acef"]
["a", "z"]

这就和题目期望一模一样。

时间复杂度分析

假设我们有 n 个字符串，每个字符串长度最多 k：

• 外层遍历所有字符串是 O(n)
• 内层处理每个字符串生成 key 是 O(k)

所以总体复杂度是 O(n * k)

空间复杂度分析

我们用了一个字典来分组，最坏情况下每个字符串都分一组，字典大小也是 O(n * k)（因为 key 是字符串差值序列）

总结

这题核心是找出规律：“移位”的本质就是字符间的差值一致。不需要真的去“移”字符串，只要你能拿到这个差值序列，你就能判断两个字符串是不是一个套路。

另外也提醒我们，在实际开发中处理字符串聚类或异常识别时，找对特征比暴力匹配要高效得多。这个题的差值 key 就是一个很实用的“特征”。

如果你在做一些输入推荐、内容防刷、文本归类功能，不妨试试看用类似的方式去做聚类、查重或识别。