389. Find the Difference.md

389. Find the Difference

思路

分别记录两个字符串中每个字符的出现次数，最后比较一下字符的出现次数，次数差1对应的字符即所求。
因为全是小写字母，所以开辟一个大小为26的数组进行计数即可。另外，没必要开辟两个计数数组，用一个数组记录即可，对s中出现的字符进行次数累加，对t中出现的字符进行次数累减。 最后次数为-1的对应的字母即所求。
时间复杂度O(n)， 空间复杂度O(1)

C++

class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int>count(26, 0);
        for(int i = 0; i < s.size(); i++){
            count[s[i] - 'a']++;
            count[t[i] - 'a']--;
        }
        count[t[t.size() - 1] - 'a']--;
        for(int i = 0; i < 26; i++)
            if(count[i] == -1) return char(i + 'a');
    }
};