Leetcode 389.找不同

发表于 | 更新于 | 分类于

题目描述

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

输入：
s = "abcd"
t = "abcde"

输出：
e

解释：
'e' 是那个被添加的字母。

题目分析

不用位运算的做法是遍历字符串t, 将t中每一个字符的出现次数存入哈希表, 而后遍历字符串s, 减去每个字符出现次数, 找到那个出现次数为1的字符.

使用位运算做法则是初始化结果res为0, 对s和t的每一位与res取异或, 最后res的值便是多出来的字符.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution { // 不用位运算
public:
    unordered_map<char, int> m;
    string::iterator it;
    char findTheDifference(string s, string t) {
        for(char c='a'; c<='z'; ++c) { // 初始化哈希表m
            m[c] = 0;
        }

        it = t.begin();

        while(it != t.end()) {
            m[*it] = m[*it]+1;
            it++;
        }

        it = s.begin();

        while(it != s.end()) {
            m[*it] = m[*it]-1;
            it++;
        }

        for(char c='a'; c<='z'; ++c) {
            if(m[c] != 0) return c;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution { // 使用位运算
public:
    char findTheDifference(string s, string t) {
        char c = 0; // 初始化结果res为0
        s.push_back(0); // 统一s和t的字符数
        for(int i=0; i<t.size(); ++i) {
            c ^= s[i]; // 对res和s[i]取异或
            c ^= t[i]; // 对res和t[i]取异或
        }
        return c;
    }
};
0%