# LeetCode 算法题 – 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.

## 分析

• 字符串 t 的字母总数比 s 多 1
• 字符串 t 的字母类别数和 s 相同或多 1

## 实现

### 实现一

`````` 1func findTheDifferenceMap(s string, t string) byte {
2    m := make(map[byte]int, len(s))
3    for i := 0; i < len(s); i++ {
4        m[s[i]] += 1
5    }
6
7    var b byte
8    for i := 0; i < len(t); i++ {
9        if count, ok := m[t[i]]; !ok || count <= 0 {
10            b = t[i]
11            break
12        } else {
13            m[t[i]] -= 1
14        }
15    }
16
17    return b
18}
``````

### 实现二

``````1func findTheDifferenceXOR(s string, t string) byte {
2    var b byte
3    for i := 0; i < len(s); i++ {
4        b ^= s[i] ^ t[i]
5    }
6    b ^= t[len(t)-1]
7
8    return b
9}
``````

### 性能

`````` 1type pair struct {
2    s string
3    t string
4}
5
6var pairs = []pair{
7    {"abcd", "abcde"},
8    {"abcd", "aebcd"},
9    {"abcd", "abecd"},
10    {"abcd", "abced"},
11}
12
13func BenchmarkFindTheDifferenceMap(b *testing.B) {
14    var p pair
15    for n := 0; n < b.N; n++ {
16        p = pairs[n%len(pairs)]
17        findTheDifferenceMap(p.s, p.t)
18    }
19}
20func BenchmarkFindTheDifferenceXOR(b *testing.B) {
21    var p pair
22    for n := 0; n < b.N; n++ {
23        p = pairs[n%len(pairs)]
24        findTheDifferenceXOR(p.s, p.t)
25    }
26}
``````

BenchmarkFindTheDifferenceMap-12 4990208 241 ns/op
BenchmarkFindTheDifferenceXOR-12 90979062 12.7 ns/op

2024年7月30日星期二 2020年2月2日星期日