Description

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.

Solutions

1. Bit manipulation

# Time: O(n)
# Space: O(1)
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        code = 0
        for ch in s + t:
            code ^= ord(ch)
        return chr(code)
# Runtime: 32 ms, faster than 65.80%
# Memory Usage: 12.8 MB, less than 100.00%

References

  1. 389. Find the Difference