389-Find the Difference

100-Same Tree | Links:

题意

You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

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

Example 2:
Input: s = "", t = "y"
Output: "y"

Example 3:
Input: s = "a", t = "aa"
Output: "a"

Example 4:
Input: s = "ae", t = "aea"
Output: "a"

思路

• 位运算：异或找唯一元素

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        # ord() 字符转换成ascii码
        # chr() ascii码转换为字符
        
        res = ord(t[-1])
        for i in range(len(s)):
            res ^= ord(s[i])
            res ^= ord(t[i])
        return chr(res)

分析:

• Time: O(n)
• Space: O(1)