389 Find the Difference

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

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

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

• 0 <= s.length <= 1000

• t.length == s.length + 1

• s and t consist of lowercase English letters.

还是简单题，因为只有26个字母，就连hashmap都省了，直接上数组。当然return的时候，要cast一下。T:O(N), N是两个string的长度。S:O(1)，int[26]。这题一个有趣的地方是，能用136 single number那一题的思路来做，用xor。同样的复杂度， T:O(N),S:O(1)

public char findTheDifference(String s, String t) {
    if (s == null || t == null) {
        return ' ';
    }
    
    int[] set = new int[26];
    for (int i = 0; i < s.length(); i++) {
        set[s.charAt(i) - 'a']++;
    }
    
    for (int i = 0; i < t.length(); i++) {
        set[t.charAt(i) - 'a']--;
    }
    
    for (int i = 0; i < 26; i++) {
        if (set[i] < 0) {
            return (char)(i + 'a');
        }
    }
    
    return ' ';
}

// xor解法，在leetcode上抄的
public char findTheDifference(String s, String t) {

    // Initialize ch with 0, because 0 ^ X = X
    // 0 when XORed with any bit would not change the bits value.
    char ch = 0;

    // XOR all the characters of both s and t.
    for (int i = 0; i < s.length(); i += 1) {
        ch ^= s.charAt(i);
    }
    for (int i = 0; i < t.length(); i += 1) {
        ch ^= t.charAt(i);
    }

    // What is left after XORing everything is the difference.
    return ch;
}