0%

LeetCode 389: Find the Difference


Difficulty: Easy

Tags: Hash Table, Bit Manipulation


问题描述

给定2个字符串s和t,t是由s打乱重组并在一个随机位置添加一个字母形成的。

找到那个新添加的字母。


解决方案

利用了字母的ASCII值。

字符串中字母的顺序并不重要。

我们知道t比s多了一个字母,其余字母尽管顺序不同但都是一样的。

那就分别把2个字符串所有的字符相加,然后t的字符和减去s的字符和得到的数字,就是新添加的字符的ASCII值。


▷ Time Complexity: O(n)

▷ Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
char findTheDifference(string s, string t) {
int vs = 0;
int vt = 0;

for(int i=0; i<s.size(); i++)
vs += s[i];

for(int j=0; j<t.size(); j++)
vt += t[j];

char res = vt - vs;

return res;
}
};

回到 Conquer Leetcode