leetcode 找不同

389. 找不同

已解答

简单

相关标签

相关企业

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

示例 2：

输入：s = "", t = "y"
输出："y"

提示：

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s 和 t 只包含小写字母

class Solution:def findTheDifference(self, s: str, t: str) -> str:# 将字符串s中的字符进行排序，并在末尾添加一个空格，以便在后续的比较中能够区分s和t的不同s = sorted(s) + [' ']# 将字符串t中的字符进行排序t = sorted(t)# 使用zip函数同时迭代两个排序后的字符串列表for i, b in zip(s, t):# 如果在迭代过程中发现两个字符串的对应字符不相等if i != b:# 返回t中的那个不同的字符return b

要找出在字符串 t 中被添加的字母，我们可以利用字符频率的概念。由于 s 和 t 只包含小写字母，我们可以创建一个计数器来统计 s 中每个字母出现的次数，然后遍历 t 并更新这个计数器。最后，那个在 t 中出现次数比 s 多一次的字母就是被添加的字母。

以下是解决这个问题的算法步骤：

1. 创建一个大小为26的数组 count，用于存储每个字母的频率，初始值都为0。
2. 遍历字符串 s，对于 s 中的每个字符，增加 count 数组中对应字母的计数。
3. 遍历字符串 t，对于 t 中的每个字符，如果 count 数组中对应字母的计数不为0，就减1，直到找到计数为0的字母，这个字母就是被添加的字母。
4. 返回找到的被添加的字母。

class Solution:def findTheDifference(self, s: str, t: str) -> str:count = [0] * 26  # 初始化计数器数组for char in s:   # 遍历字符串scount[ord(char) - ord('a')] += 1  # 更新s中每个字母的计数for char in t:   # 遍历字符串tif count[ord(char) - ord('a')] == 0:  # 如果计数为0，说明是被添加的字母return charelse:count[ord(char) - ord('a')] -= 1  # 否则，更新计数

class Solution:def findTheDifference(self, s: str, t: str) -> str:return (Counter(t) - Counter(s)).popitem()[0]

使用了 Python 的 collections 模块中的 Counter 类来统计字符串中每个字符的出现次数。

1. class Solution: 定义了一个名为 Solution 的类，这个类将包含解决这个问题的方法。

2. def findTheDifference(self, s: str, t: str) -> str: 定义了一个名为 findTheDifference 的方法，它接受两个字符串参数 s 和 t，并返回一个字符串，即在 t 中被添加的字母。

3. return (Counter(t) - Counter(s)).popitem()[0] 是这个方法的核心逻辑：

   • Counter(t) 创建一个 Counter 对象，统计字符串 t 中每个字符的出现次数。
   • Counter(s) 创建另一个 Counter 对象，统计字符串 s 中每个字符的出现次数。
   • Counter(t) - Counter(s) 执行两个 Counter 对象的差集操作，结果是一个 Counter 对象，其中包含在 t 中出现次数多于 s 的字符及其出现次数。
   • .popitem() 方法从 Counter 对象中弹出（并返回）一个包含键值对的元组，这个键值对是 Counter 对象中的一个项。由于我们只关心那个多出来的字符，所以这里使用 popitem() 方法来获取这个字符。
   • [0] 表示返回元组中的第一个元素，即字符本身。

这段代码的逻辑是，由于 t 是由 s 随机重排后添加一个字母形成的，所以 t 中多出来的那个字母在 Counter(t) 中的计数会比 Counter(s) 中的计数多1。通过计算两个 Counter 对象的差集，我们可以直接找到这个多出来的字母。

这种方法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为我们需要遍历整个字符串来构建 Counter 对象。空间复杂度也是 O(n)，因为我们需要存储两个字符串中所有字符的计数。