What is the optimal approach for the Find the Difference problem?

The XOR method is optimal because it runs in linear time and constant space, making it faster and more space-efficient than other methods like sorting or using a hash table.

How does XOR solve the Find the Difference problem?

XOR-ing all the characters in both strings will cancel out the matching characters, leaving the extra character as the result. This technique ensures a time complexity of O(n) and space complexity of O(1).

Can I solve this problem with just a hash table?

Yes, using a hash table is a valid approach. By counting the frequency of each character in both strings, you can identify the extra letter in O(n) time, but this method uses extra space for the hash table.

What are the limitations of sorting as a solution?

Sorting both strings has a time complexity of O(n log n), which is less efficient compared to the linear time solutions using XOR or hash tables.

What other variants could this problem have?

This problem can be extended by adding more characters to string t, testing scalability, or considering larger strings that might require optimization techniques.

#389

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

找不同

给定两个字符串 s 和 t ，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。示例 1：输入： s = "abcd", t = "abcde" 输出： "e" 解释： 'e' 是那个被添加的字母。示例 2：输入： s = …

哈希表字符串位运算排序

题目描述

给定两个字符串 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 只包含小写字母

lightbulb

解题思路

方法一：计数

我们可以用一个哈希表或数组 $cnt$ 统计字符串 $s$ 中每个字符出现的次数，再遍历字符串 $t$ ，对于每个字符，我们在 $cnt$ 中减去一次出现的次数，如果对应次数为负数，则说明该字符在 $t$ 中出现的次数大于在 $s$ 中出现的次数，因此该字符为被添加的字符。

时间复杂度 $O(n)$ ，空间复杂度 $O(|\Sigma|)$ ，其中 $n$ 为字符串的长度，而 $\Sigma$ 表示字符集，这里字符集为所有小写字母，所以 $|\Sigma|=26$ 。

1

2

3

4

5

6

7

8

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cnt = Counter(s)
        for c in t:
            cnt[c] -= 1
            if cnt[c] < 0:
                return c

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate chooses a hash table or XOR-based approach for linear time performance.
question_mark
The candidate uses sorting without considering time complexity trade-offs.
question_mark
The candidate effectively explains the space-time trade-off between the hash table and XOR solutions.

warning

常见陷阱

外企场景

error
Using sorting without considering its time complexity can lead to suboptimal solutions.
error
Not recognizing that XOR can efficiently solve the problem in O(1) space.
error
Overcomplicating the solution with unnecessary steps when a simple hash table or XOR solution suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem could involve finding the missing character from a set of strings, rather than two strings.
arrow_right_alt
An extension could involve multiple additional characters being added to t, increasing the complexity.
arrow_right_alt
Consider a scenario where both strings are very large, testing the scalability of different approaches.

help

常见问题

外企场景

继续练习

#451 根据字符出现频率排序 #268 丢失的数字 #522 最长特殊序列 II