Find the Difference 389

Question:

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.

Solution:

这道题最naive的想法就是用一个hashmap记录s中所有出现过的字符及其次数，再遍历t将出现的字符次数减1。最后次数不为0的即为新出现的字符。但是这样要用额外空间保存map。

这道题的另外一个方法是将其看作找single number那道题，因为s和t中除了新加入的字符只出现奇数次，其他字符都出现偶数次。因此，和single number那道题一样，只要让所有字符（本质是数字）相互做异或操作，最后剩下的就是新加入的字符。

代码如下：

public class Solution {
    public char findTheDifference(String s, String t) {
        //bit manipulation, just like find the single number while others appear twice
        int n = t.length();
        char c = t.charAt(n - 1);
        for (int i = 0; i < n - 1; i++) {
            c ^= s.charAt(i);
            c ^= t.charAt(i);
        }
        return c;
    }
}