# -*- coding: utf-8 -*-

"""
Find the Difference
===================

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

import collections


class Solution(object):
    """算法思路：

    利用hash table记录每个字母出现的次数，最后多出来的那个即为结果

    Time: O(n)
    Space: O(n)
    """
    def findTheDifference(self, s, t):
        table = collections.defaultdict(int)

        for i in xrange(len(t)):
            table[t[i]] += 1

            if i < len(s):
                table[s[i]] -= 1

        return [k for k, v in table.items() if v][0]


class Solution(object):
    """算法思路：

    利用异或去重
    """
    def findTheDifference(self, s, t):
        r = ord(t[-1])
        for i in xrange(len(s)):
            r ^= ord(s[i])
            r ^= ord(t[i])
        return chr(r)


s = Solution()
print s.findTheDifference("", "a")
print s.findTheDifference("aaa", "aaaa")
print s.findTheDifference("abcd", "bdace")
