LeetCode 题解工作台
差值数组不同的字符串
给你一个字符串数组 words ，每一个字符串长度都相同，令所有字符串的长度都为 n 。 每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i] ，其中对于 0 有 difference[i][j] = words[i][j+1] - word…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们用哈希表 维护字符串的差值数组和字符串的映射关系，其中差值数组为字符串的相邻字符的差值构成的数组。由于题目保证了除了一个字符串以外，其他字符串的差值数组都相同，因此我们只需要找到差值数组不同的字符串即可。 时间复杂度 $O(m \times n)$，空间复杂度 $O(m + n)$。其中 和 分别为字符串的长度和字符串的个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个字符串数组 words ，每一个字符串长度都相同，令所有字符串的长度都为 n 。
每个字符串 words[i] 可以被转化为一个长度为 n - 1 的 差值整数数组 difference[i] ，其中对于 0 <= j <= n - 2 有 difference[i][j] = words[i][j+1] - words[i][j] 。注意两个字母的差值定义为它们在字母表中 位置 之差，也就是说 'a' 的位置是 0 ，'b' 的位置是 1 ，'z' 的位置是 25 。
- 比方说，字符串
"acb"的差值整数数组是[2 - 0, 1 - 2] = [2, -1]。
words 中所有字符串 除了一个字符串以外 ，其他字符串的差值整数数组都相同。你需要找到那个不同的字符串。
请你返回 words中 差值整数数组 不同的字符串。
示例 1：
输入：words = ["adc","wzy","abc"] 输出："abc" 解释： - "adc" 的差值整数数组是 [3 - 0, 2 - 3] = [3, -1] 。 - "wzy" 的差值整数数组是 [25 - 22, 24 - 25]= [3, -1] 。 - "abc" 的差值整数数组是 [1 - 0, 2 - 1] = [1, 1] 。 不同的数组是 [1, 1]，所以返回对应的字符串，"abc"。
示例 2：
输入：words = ["aaa","bob","ccc","ddd"] 输出："bob" 解释：除了 "bob" 的差值整数数组是 [13, -13] 以外，其他字符串的差值整数数组都是 [0, 0] 。
提示：
3 <= words.length <= 100n == words[i].length2 <= n <= 20words[i]只含有小写英文字母。
解题思路
方法一：哈希表模拟
我们用哈希表 维护字符串的差值数组和字符串的映射关系，其中差值数组为字符串的相邻字符的差值构成的数组。由于题目保证了除了一个字符串以外，其他字符串的差值数组都相同，因此我们只需要找到差值数组不同的字符串即可。
时间复杂度 ，空间复杂度 。其中 和 分别为字符串的长度和字符串的个数。
class Solution:
def oddString(self, words: List[str]) -> str:
d = defaultdict(list)
for s in words:
t = tuple(ord(b) - ord(a) for a, b in pairwise(s))
d[t].append(s)
return next(ss[0] for ss in d.values() if len(ss) == 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m * n) where m is the number of strings and n is their length, as each string is scanned once. Space complexity is O(m * n) due to storing difference arrays in the hash table for uniqueness detection. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask how to convert letters to numeric differences efficiently.
- question_mark
They may check if you can detect the single outlier using minimal comparisons.
- question_mark
They might probe alternative ways to store and compare difference arrays compactly.
常见陷阱
外企场景- error
Forgetting that alphabet positions start at zero for 'a'.
- error
Comparing strings directly instead of their difference arrays, missing the true pattern.
- error
Using nested loops to compare every array pair, which is inefficient for larger inputs.
进阶变体
外企场景- arrow_right_alt
Strings of varying lengths where you must normalize or pad differences.
- arrow_right_alt
Finding multiple odd strings if more than one difference array occurs once.
- arrow_right_alt
Using modulo 26 differences for circular alphabet calculations.