Given two strings s and t which consist of only lowercase letters.
String t is generated by random shuffling string s (随机打乱字符串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.
char findTheDifference(string s, string t)
1、把字符串s随机打乱,然后在任意位置添加一个字母,构成字符串t。要找出这个添加的字母。这道题不难。
2、传统方法:
定义一个数组来统计s中每个字母出现的次数,做一次遍历。
然后再对字符串t做一次遍历,碰到出现的字母,数组中对应的数值就减一。
最后再对数组做一次遍历,数组中不为0的那个数就是我们要找的字母。
3、改进1:
因为字母本身在计算机中存储是以ASCII码存储的,所以我们也可以不用定义数组,直接对字符串s做一次遍历,计算出各个字母的和。
然后再对字符串t做一次遍历,计算出各个字母的和。
最后相减得到的值就是我们要找的只出现了一次的字母。
代码如下:
char findTheDifference(string s, string t)
{
char result=0;
for(int i=0;i<s.size();i++)
result+=s[i];
for(int i=0;i<t.size();i++)
result-=t[i];
return -result;
}
时间复杂度O(n),实测6ms,beats 87.34% of cpp submissions。
4、改进2:
我们要找的其实是只出现了一次的字母,其余字母都出现了两次,所以这道题我们可以用异或处理。
关于为什么可以用异或处理,推荐前文leetcode-136-Single Number,讲解得比较透彻。
代码如下:
char findTheDifference(string s, string t)
{
char result=0;
for(int i=0;i<s.size();i++)
{
result^=s[i];//**
result^=t[i];//**
}
result^=t[t.size()-1];
return result;
}
上述代码时间复杂度仍然是O(n),实测6ms,beats 87.34% of cpp submissions。
5、相关问题说明:
3中代码可能会出现result这个数值溢出的问题,当字符串很长的时候。反观4中代码,由于采取的是异或的方法,所以字符串多长都不会溢出。
异或还是更加好使呀,而且这道题假如将两个字符串拼接成一个,然后要找出那个我们添加上去的字母,那个只出现一次的字母,还是只能用异或(O(n)的时间复杂度,O(1)的空间复杂度)。