find-the-difference.py

"""

389. Find the Difference
Easy

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"
 

Constraints:

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

"""


# V0
# IDEA : COLLECTIONS + DICT 
import collections
class Solution(object):
    def findTheDifference(self, s, t):
        cnt_s = collections.Counter(s)
        cnt_t = collections.Counter(t)
        res = [x for x in cnt_t.keys() if x not in cnt_s.keys() or cnt_t[x] != cnt_s[x]]
        #print (res)
        return res[0]

# V1 
# http://bookshadow.com/weblog/2016/08/28/leetcode-find-the-difference/
# IDEA : COLLECTIONS + DICT 
# In [23]: x
# Out[23]: [1, 1, 1, 2, 3]

# In [24]: y
# Out[24]: [1, 1, 1, 2]

# In [25]: ds = collections.Counter(x)

# In [26]: dt = collections.Counter(y)

# In [27]: ds
# Out[27]: Counter({1: 3, 2: 1, 3: 1})

# In [28]: dt
# Out[28]: Counter({1: 3, 2: 1})

# In [29]: ds-dt
# Out[29]: Counter({3: 1})

# In [30]: (ds-dt).keys()
# Out[30]: dict_keys([3])
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        ds = collections.Counter(s)
        dt = collections.Counter(t)
        return (dt - ds).keys().pop()

# V2 
# Time:  O(n)
# Space: O(1)
import operator
import collections
from functools import reduce
class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        return chr(reduce(operator.xor, map(ord, s), 0) ^ reduce(operator.xor, map(ord, t), 0))

    def findTheDifference2(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        t = list(t)
        s = list(s)
        for i in s:
            t.remove(i)
        return t[0]

    def findTheDifference3(self, s, t):
        return chr(reduce(operator.xor, map(ord, s + t)))

    def findTheDifference4(self, s, t):
        return list((collections.Counter(t) - collections.Counter(s)))[0]

    def findTheDifference5(self, s, t):
        s, t = sorted(s), sorted(t)
        return t[-1] if s == t[:-1] else [x[1] for x in zip(s, t) if x[0] != x[1]][0]