LeetCode 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. Example:

Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.

---

有两个字符串s和t，其中t是由s shuffle而来，并且在随机位置上随机加上了一个字符，现在要找出这个随机加上的字符是哪个。 第一思路是，t由s shuffle而来的部分和s的组成是一样的，只是字符排列顺序不一样，所以每个字符出现的次数是一样的，而加上的那个字符导致该字符的出现次数在s和t中不一样，所以用一个hash就可以找到这个出现次数不一样的字符。 完整代码如下： [cpp] class Solution { public: char findTheDifference(string s, string t) { unordered_map<char, size_t> mpS, mpT; for (int i = 0; i < s.size(); i++) { mpS[s[i]]++; } for (int i = 0; i < t.size(); i++) { mpT[t[i]]++; } unordered_map<char, size_t>::iterator it = mpT.begin(); while (it != mpT.end()) { if (mpS.find((*it).first) == mpS.end() || mpS[(*it).first] != (*it).second)return (*it).first; it++; } return 0; // never reach here } }; [/cpp] 本代码提交AC，用时13MS。 后来想到之前做的一个题LeetCode Single Number，把s和t组合起来，不就相当于除了加入的字符，其他字符都重复出现了偶数次吗，所以把s和t中的所有字符异或一下，得到的结果就是那个插入的字符，真是高明。 完整代码如下： [cpp] class Solution { public: char findTheDifference(string s, string t) { char ans = 0; for (int i = 0; i < s.size(); i++) { ans ^= s[i]; } for (int i = 0; i < t.size(); i++) { ans ^= t[i]; } return ans; } }; [/cpp] 本代码提交AC，用时3MS，相当于前一个版本的零头，果然位运算的效率就是高。]]>