389. Find the Difference 找不同

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

---

@TOC

[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 日 —— 这么快就到双十一了？？