給定兩個只包含小寫字母的字符串 s 和 t，其中字符串 t 是由字符串 s 亂序後，再在隨機位置添加一個字母而成，請找到該隨機添加的字母。
例如：s = abcd, t = abcde, 其中 e 是隨機添加的字母。
其實這個例子不夠明確，又比如 s = abcde, t = aedceb, 隨機添加的字母還是 e。
原題
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
實現
實現一
依題意，用 map[byte]int 存儲字符串 s 中每個字母出現的次數，如果字符串 t 中某個字母不存在於 map 或出現次數過多，則該字母為隨機添加的字母。
時間複雜度： O(n)
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}
實現二
可以利用 XOR 解決
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
雖然測試不嚴謹，不過後者性能更高。
