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

一开始，我尝试用 hashMap 的方法来做此题，但是 hashmap 的 key 是唯一的，而此题会的输入 string 会包括相同的字符，因此不使用 hashmap。
于是，我想到了 CS180 和 CS240 都提到的数字符串里每个支付的方法，建立一个和 ASCII 表一样大的整数数组，以字符串的值作为下标记录每个字符串出现的次数，第一遍过 input的时候++，过一遍 target 的时候--，就能得到多出来的字符是哪个了。
My solution:

public class Solution {
    public char findTheDifference(String s, String t) {
        int[] alphabet = new int[256];
        for(int i = 0; i < s.length(); i++) {
            alphabet[s.charAt(i)]++;
        }

        for (int i = 0; i < t.length(); i++) {
            alphabet[t.charAt(i)]--;
        }

        for (int i = 0; i < alphabet.length; i++){
            if(alphabet[i] == -1) {
                return (char)i;
            }
        }

        return '0';
        
    }
}

后来看到别人的方法，才恍然大悟，这个题目其实和之前做的 hamming distance 并无本质区别，hamming distance 是计算两个整数之间不同的 bit 的数目，而本题是计算两个字符串中多出来的一个字符。
因此，在这里，我们完全可以再次前几个 blog 里提到的关于异或的重要性质：即 A ^ A = 0。

public char findTheDifference(String s, String t) {
    char c = 0;
    for (int i = 0; i < s.length(); ++i) {
        c ^= s.charAt(i);
    }
    for (int i = 0; i < t.length(); ++i) {
        c ^= t.charAt(i);
    }
    return c;
}

maybe a more elegant version:

public char findTheDifference(String s, String t) {
    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;
}