差值数组不同的字符串

难度: Easy

给你一个字符串数组 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 <= 100
n == words[i].length
2 <= n <= 20
words[i] 只含有小写英文字母。

Submission

运行时间: 26 ms

内存: 15.9 MB

class Solution:
    def oddString(self, words: List[str]) -> str:
        s = {}
        for word in words:
            a = []
            for i in range(1, len(word)):
                a.append(ord(word[i]) - ord(word[i-1]))
            if s.get(str(a)) is None:
                s[str(a)] = [word]
            else:
                s[str(a)].append(word)
        for value in s.values():
            if len(value) == 1:
                return value[0]

Explain

题解的核心思路是首先计算每个单词的差值数组，然后使用一个字典来记录所有差值数组出现的次数。每个差值数组转换成字符串作为字典的键，对应的值是包含相同差值数组的单词列表。遍历字典，找到只出现一次的差值数组，返回对应的单词即可。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def oddString(self, words: List[str]) -> str:
        s = {} # 字典用于存储差值数组和对应的单词列表
        for word in words: # 遍历单词列表
            a = [] # 存储当前单词的差值数组
            for i in range(1, len(word)): # 计算差值数组
                a.append(ord(word[i]) - ord(word[i-1]))
            if s.get(str(a)) is None: # 如果差值数组不在字典中，则添加
                s[str(a)] = [word]
            else: # 如果已存在，则添加到对应的列表中
                s[str(a)].append(word)
        for value in s.values(): # 遍历字典的值
            if len(value) == 1: # 如果列表长度为1，说明这是唯一的差值数组
                return value[0] # 返回对应的单词

Explore

在计算差值数组时，选择将每个字符的ASCII值相减是为了捕捉单词中字符顺序的变化，这样可以有效地识别和区分具有不同字符模式的单词。如果仅使用字符的索引差异，那么就会丢失关于字符实际顺序的信息，使得算法无法区分具有不同字符但相同长度的单词。例如，单词'abc'和'acb'的索引差异相同，但它们的字符顺序不同，通过ASCII值的差值可以区别这种差异。

在Python中，字典的键必须是不可变类型，而列表是可变的，因此不能直接用作字典的键。将差值数组转换为字符串是一种绕过这一限制的方法，因为字符串是不可变的，可以作为字典的键。此外，将差值数组转换为字符串还便于比较和存储，因为字符串形式的表示是唯一的，便于检索和匹配。

如果所有单词的差值数组都相同，那么每个差值数组对应的列表中将包含所有单词，这意味着没有任何列表的长度会是1。在这种情况下，题解中的算法将无法找到只出现一次的差值数组，因为不存在这样的数组。因此，算法在这种特殊情况下不会返回任何单词。如果需要处理这种情况，可以在算法中添加一个检查，如果没有找到任何列表长度为1，可以返回一个特定的值或错误信息。

题解中的算法没有明确指定如果存在多个只包含一个单词的列表时应该返回哪一个单词。在实际实现中，这种情况会返回遍历字典时遇到的第一个符合条件的单词。这基于字典遍历的顺序，通常是插入顺序，但这种行为可能依赖于具体的Python版本和实现。如果需要更明确的行为，可以修改算法来返回所有符合条件的单词列表，或者定义其他规则来选择返回哪个单词。