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

虽然测试不严谨,不过后者性能更高。

razonyang
2024年11月24日星期日 2020年2月2日星期日