0389.find_the_difference.md

0389.找不同

题目链接

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

` 输入： s = "abcd" t = "abcde"

输出： e

解释： 'e' 是那个被添加的字母。 `

简单思路

统计字符串s和t中每个字母出现的次数并分别存入字典中，通过比较两个字典，得出被添加的字母，复杂度略大于$O(m+n)$，执行时间48ms

class Solution:
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
           
        sWordDict = dict()
        tWordDict = dict()
        
        for word in s:
            try:
                sWordDict[word] += 1
            except:
                sWordDict[word] = 0
                
        for word in t:
            try:
                tWordDict[word] += 1
            except:
                tWordDict[word] = 0
        
        for word, cnt in tWordDict.items():
            try:
                # if the adding word in s
                if sWordDict[word] != cnt:
                    return word
            except:
                # if the adding word not in s
                return word

然而

注意异或操作，对于数字，其与自身进行异或操作时为0，否则不为0，可以起到对于相同元素抵消的作用，而题目中t与s在组成元素上，恰好仅有一位不同，所以对s和t的每个字符进行异或操作即可，复杂度$O(m+n)$，执行时间44ms

class Solution:
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        
        res = 0
        
        for ch in s + t:
            res ^= ord(ch)
        
        return chr(res)

唉，我还是太年轻。