LeetCode 算法題 – Find The Difference

本頁內容

給定兩個只包含小寫字母的字符串 st,其中字符串 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

雖然測試不嚴謹,不過後者性能更高。