# LeetCode Solution, Easy, 389. Find the Difference

# [389. Find the Difference](https://leetcode.com/problems/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.

#### 題目翻譯

會給兩個字串變數 `s` 和 `t`，其中 `t` 是由 `s` 和一個隨機的字串插入到隨機的位置所組成的。要找出是哪個字母。

### 解法解析

這題主要就是可以使用最多三個，最少一個迴圈來處理。最主要的判斷是在最後的一個迴圈，在其中有許多不同的判斷方式，常見的會有：比較 index、比較字母的數量、比較兩個字母的 ASCII Code、Bit operator

比較 Index 的方式，可以參考 Swift 的範例。比較字母的數量，參考 Python count 的範例，我覺得是最好理解的解法。ASCII Code 的話，因為不同的字母會是不同的數值，所以 `s` 和 `t` 加總後相減就是多出來的字母，這個解法也是滿好懂的，可以參考 Kotlin 的範例。最後的 Bit operator 的作法是比較需要思考的。

依照 XOR 的特性
```
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
```

所以同字母的最後會相消，所以最後留下來的數值就會是多插入的字母

#### 程式範例

##### Go

```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

```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

```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

```python
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

```python
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

```python
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

```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)
    }
}
```