LeetCode389 Find the Difference

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

样例

1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

思路

给两个只含小写字母的字符串s和t,其中串t为串s打乱之后的某一排列,同时在某一随机位置新增一个字符。现在要找到这一新增的字符。

一个直观的想法是开一个数组记录s中每个字母出现的次数,然后再开一个数组也记录t中每个字母出现的次数,然后比较一下哪个字母的个数不一样,即为新增的字符。

如果之前做过LeetCode136 Single Number这道题的话,那么另一个想法就是考虑能不能把字符串也进行异或呢,剩下的不就是那个“Single Char”了吗?显然是可以的!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
char findTheDifference(string s, string t) {
int cnt1[26] = {0};
int cnt2[26] = {0};
int size = s.size();
for (int i = 0; i < size; ++i) {
cnt1[s[i] - 'a']++;
cnt2[t[i] - 'a']++;
}
cnt2[t[size] - 'a']++;
for (int i = 0; i < 26; ++i) {
if (cnt1[i] != cnt2[i]) {
return char(i + 'a');
}
}
}
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
char findTheDifference(string s, string t) {
int size = s.size();
char ch = t[size];
for (int i = 0; i < size; ++i) {
ch ^= s[i] ^ t[i];
}
return ch;
}
};
分享到 评论