题目描述
给定两个字符串 s 和 t ,它们只包含小写字母。
字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1:
输入:s = “abcd”, t = “abcde” 输出:“e” 解释:‘e’ 是那个被添加的字母。
示例 2:
输入:s = “”, t = “y” 输出:“y”
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/find-the-difference
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目难度——简单
方法一:使用哈希表计数出现次数
字符串t只比s多了一个字符,也就是说有一个字符的出现次数会比其他字符多1,那么我们就可以先遍历一次字符串s,用一个字典存储每个字母出现的次数,然后再遍历一次字符串t,遍历的同时对每个字母出现的次数减1,直到出现次数小于0的字母,返回这个字母就是答案。
代码/Python
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
table = dict()
for i in range(len(s)):
table[s[i]] = table.get(s[i], 0) + 1
for i in range(len(t)):
table[t[i]] = table.get(t[i], 0) - 1
if table[t[i]] < 0:
return t[i]
return ' '
40ms,打败70%。还能提速,两遍遍历的查询操作,加一减一操作有点多。注意不能在遍历t的时候直接table[i] -= 1,因为t有可能添加一个在s中没有出现过的字母,直接这样写的话会报错。
方法二:利用字母的ASCII码
每个字母都有特定的ASCII码值,从这个角度出发,题目就可以理解为从两串不同数字中找出第二串数字中多出的那个数字。那么我们就可以同样两次遍历字符串,用两个变量记录两个字符串中所有字母的ASCII码总和,最后返回差值代表的字母即可。
代码/C++/Python
class Solution {
public:
char findTheDifference(string s, string t) {
int totals = 0, totalt = 0;
for(auto w:s){
totals += w;
}
for(auto w:t){
totalt += w;
}
return totalt - totals;
}
};
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
totals, totalt = 0, 0
for w in s:
totals += ord(w)
for w in t:
totalt += ord(w)
return chr(totalt - totals)
方法三:位运算
根据异或运算的规则,相同为假,相异为真,t只比s多了一个字母,其他的字母全是一样的,那么如果我们把未添加新字母的t和s进行异或,最后肯定就是0。0再和任何字母异或还是那个字母本身,就得到了答案。
class Solution {
public:
char findTheDifference(string s, string t) {
int res = 0;
for(char w:s){
res ^= w;
}
for(char w:t){
res ^= w;
}
return res;
}
};
总结
三种方法都要进行两次遍历,第一种方法所做的操作要略多一点,但三种方法都是O(N)的,方法一的空间是O©,其中C是出现的字符数,最多也就是26个字母,所以是常数级别,方法二三只用到了一两个变量,所以空间算O(1)。