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

### 解法解析

``````0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
``````

#### 程式範例

##### Go
``````func findTheDifference(s string, t string) byte {
ht := make(map[byte]int, 0)
for _, ch := range []byte(t) {
ht[ch]++
}

for _, ch := range []byte(s) {
ht[ch]--
}

var result byte
var count int
for result, count = range ht {
if count > 0 {
break
}
}

return result
}
``````
##### JavaScript
``````/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function (s, t) {
let c = {};
for (const ch of s) {
c[ch] = (c[ch] || 0) + 1;
}

for (const ch of t) {
if (c[ch]) {
c[ch] = c[ch] - 1;
} else {
return ch;
}
}
};
``````
##### Kotlin
``````class Solution {
fun findTheDifference(s: String, t: String): Char {
val firstSum = s.toCharArray().sumBy { it.toInt() }
val secondSum = t.toCharArray().sumBy { it.toInt() }
return (secondSum - firstSum).toChar()
}
}
``````
##### Python
###### Bit
``````class Solution:
def findTheDifference(self, s: str, t: str) -> str:

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

# XOR all the characters of both s and t.
for char_ in s:
ch ^= ord(char_)

for char_ in t:
ch ^= ord(char_)

# What is left after XORing everything is the difference.
return chr(ch)
``````
###### Set
``````class Solution:
def findTheDifference(self, s: str, t: str) -> str:
for i in set(t):
if s.count(i) != t.count(i):
return i
``````
###### Count
``````from collections import Counter

class Solution:
def findTheDifference(self, s: str, t: str) -> str:
# Prepare a counter for string s.
# This holds the characters as keys and respective frequency as value.
counter_s = Counter(s)

# Iterate through string t and find the character which is not in s.
for ch in t:
if ch not in counter_s or counter_s[ch] == 0:
return ch
else:
# Once a match is found we reduce frequency left.
# This eliminates the possibility of a false match later.
counter_s[ch] -= 1
``````
##### Swift
``````class Solution {
func findTheDifference(_ s: String, _ t: String) -> Character {
var t = t
for ch in s {
if t.contains(ch), let index = t.firstIndex(of: ch) {
t.remove(at: index)
}
}
return Character(t)
}
}
``````