【LeetCode】389. Find the Difference 解题报告（Java & Python）

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

题目描述

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

巴特西