作者: 负雪明烛
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 日 —— 这么快就到双十一了??