LeetCode题目笔记——6225. 差值数组不同的字符串，Python 32ms

题目描述

• 这个题目是昨天晚上第90场双周赛的第一题，

给你一个字符串数组 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] 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/odd-string-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目难度——简单

方法一：记录数组的出现次数

  一开始本来想按照题目说的要求，先设一个字典，求出每个差值数组后，把这个差值数组作为键，对应字符串的数组作为值，形成一个字典，但是python不允许用列表来作为字典的键，所以又想用元组来作为键，因为元组类型是不可变对象，所以可以作为键。再另辟蹊径，对应不同的字符串作为一个数组的话，有点浪费空间，还不好用，那要怎么体现出他们之间的差异性呢？既然M个字符串的长度都是n，而M-1个字符串的差值数组又是一样的，那我们就可以把这些一样的字符串给他加起来，再作为差值数组（元组）的键值，最后只会有一个键值的长度是n，返回那个键值就是答案。

代码/Python

class Solution:
    def oddString(self, words: List[str]) -> str:
        n = len(words[0])
        table = dict()
        for word in words:
            tmp = [0] * (n - 1)
            for i in range(n - 1):
                tmp[i] = ord(word[i + 1]) - ord(word[i])
            tmp = tuple(tmp)
            table[tmp] = table.get(tmp, '') + word
        
        for item in table.items():
            if len(item[1]) == n:
                return item[1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

  只需要遍历一次数组words，生成差值数组也只是常数时间的，所以时间是O(N)，用到了字典，所以空间是O(N)。