'''
Level: Easy  Tag: [Bit Manipulation]

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.

Constraints:

0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lowercase English letters
'''


class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if len(s) == 0:
            return t
        elif len(t) == 0:
            return s
        lstT = list(t)
        lstS = list(s)
        while lstS:
            lstT.pop(lstT.index(lstS.pop()))
        return lstT.pop()

    '''
    XOR運算
    XOR比較兩個數字時，如果兩個數字相同的話結果會是0
    所以比較到最後的數字一定是多出來的那個字元
    '''

    def findTheDifference_xor(self, s, t):
        x = 0
        for c in s:
            x ^= ord(c)

        for c in t:
            x ^= ord(c)

        ans = chr(x)
        print(ans)
        return ans


s = "abcd"
t = "abcde"

print(Solution().findTheDifference(s, t))
print(Solution().findTheDifference_xor(s, t))