【LeetCode】389. Find the Difference 解题报告(Java & Python)

作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/


[LeetCode]

https://leetcode.com/problems/find-the-difference/

  • Difficulty: Easy

题目描述

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde" Output:
e Explanation:
'e' is the letter that was added.

题目大意

字符串t是字符串s打乱顺序之后,又随机添加了一个字符,求这个字符。

解题方法

方法一:字典统计次数

题目没有要求空间复杂度,因此可以用HashTable记录每个元素出现的次数,最后只出现了一次的就是那个被添加上去的元素。不提。

另外,可以用一个数组,把两个字符串中出现了的字符对应到数组当中,把s数组对应位置++,t对应位置–,出现了两次的元素则会抵消,否则,就是出现了一次的。

java解法如下:

public class Solution {
public char findTheDifference(String s, String t) {
int[] chars=new int[26];
for(int i=0; i<s.length(); i++){
chars[s.charAt(i) - 'a']++;
}
for(int i=0; i<t.length(); i++){
chars[t.charAt(i) - 'a']--;
}
for(int i=0; i<chars.length; i++){
if(chars[i]!=0){
return (char) ('a' + i);
}
}
return '0';
}
}

AC:9ms

python写法如下:

class Solution:
def findTheDifference(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
scount, tcount = collections.Counter(s), collections.Counter(t)
for t in tcount:
if tcount[t] > scount[t]:
return t

方法二:异或

想到了之前做的那个题,数组中其余元素出现了两次,找出数组中只出现了一次的那个数字。完完全全一样的题目。

方法是异或运算。

public class Solution {
public char findTheDifference(String s, String t) {
int answer = 0;
for(int i=0; i<s.length(); i++){
answer ^= s.charAt(i) - 'a';
}
for(int i=0; i<t.length(); i++){
answer ^= t.charAt(i) - 'a';
}
return (char) ('a' + answer);
}
}

AC:9ms

python写法如下:

class Solution(object):
def findTheDifference(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
return chr(reduce(lambda x, y : x ^ y, map(ord, s + t)))

方法三:排序

把字符串转成了列表,然后进行排序,从前向后遍历slist,如果tlist的该位置和slist不同,那么这个就是tlist添加出来的字符。如果遍历结束没有找到,那么tlist最后的字符就是答案。

class Solution:
def findTheDifference(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
slist, tlist = list(s), list(t)
slist.sort()
tlist.sort()
for i in range(len(slist)):
if slist[i] != tlist[i]:
return tlist[i]
return tlist[-1]

日期

2017 年 1 月 7 日
2018 年 11 月 10 日 —— 这么快就到双十一了??

上一篇:LeetCode 389. Find the Difference (找到不同)


下一篇:LeetCode: 389 Find the Difference(easy)