__author__ = 'Hk4Fun'
__date__ = '2018/5/10 17:11'
'''题目描述：
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.
'''
'''主要思路：
思路1：
leetcode/hash table/easy/242. Valid Anagram.py
时间O（n+m），空间O（1）
多出来的那个字母不管是已经在s中存在的还是新的，
在遍历t时一定会把该个字母的计数减为-1：
如果是s中存在的字母，则第二次遍历到该字母时会被减为-1
如果是新的字母，遍历到它时就直接减为-1了

思路2：pythonic，利用collections.Counter的减法
Counter的减法不只是单单地做差集，况且原生的dict是不支持减法操作的，set才可以
Counter会把不同的键保留，相同的键对应的值进行减法运算，<=0则从结果集从去掉，
所以不管多出来的那个字母在s中存在的还是新的，最终都会在Counter(t)-Counter(s)中保留下来
'''

from collections import Counter
class Solution:
    """
    :type s: str
    :type t: str
    :rtype: str
    """
    def findTheDifference1(self, s, t):
        table = [0] * 26
        for i in s:
            table[ord(i) - ord('a')] += 1
        for i in t:
            index = ord(i) - ord('a')
            table[index] -= 1
            if table[index] == -1: return i

    def findTheDifference(self, s, t):
        return list(Counter(t) - Counter(s))[0]


# ================================测试代码================================
from Test import Test


class MyTest(Test):
    def my_test_code(self):
        self.debug = False  # debug为True时每个测试用例只测试一遍，默认情况下关闭debug模式
        self.TEST_NUM = 1  # 单个测试用例的测试次数, 只有在debug为False的情况下生效
        testArgs = []
        # 只需在此处填写自己的测试代码
        # testArgs中每一项是一次测试，每一项由两部分构成
        # 第一部分为被测试函数的参数，第二部分只有最后一个，为正确答案

        testArgs.append([])
        testArgs.append([])
        testArgs.append([])
        testArgs.append([])
        testArgs.append([])
        testArgs.append([])
        testArgs.append([])
        testArgs.append([])
        testArgs.append([])
        testArgs.append([])

        return testArgs

    def convert(self, result, *func_arg):
        # 在此处填写转换函数，将测试结果转换成其他形式
        return result

    def checked(self, result, expected, *func_arg):
        # 在此处填写比较器，测试返回的结果是否正确
        return result == expected


if __name__ == '__main__':
    MyTest(Solution()).start_test()