find-the-difference.py

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

# 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.

import operator
import collections


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]


if __name__ == '__main__':
    s = Solution()
    r = s.findTheDifference2('abcd', 'abcde')
    print r