1.题目大意
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.
给定两个字符串,有其中一个字符串有一个多出来的字符,找出那个字符。这题的Example依然是给的不大好,下面再给一个example:
Input:
s = "adbc"
t = "bacde" Output:
e
2.思路
这题思路比较简单,下面提供几个思路,第一个是我的原始思路,利用字母实际上是基于ASCII代码,可以转换为十进制数字来计算的。
class Solution
{
public:
char findTheDifference(string s, string t)
{
int sum=0;
char ch;
if(s.size()>t.size()) swap(t,s); //s is the small one
for(int i=0; i<s.size(); i++)
{
sum-=(s[i]);
sum+=(t[i]);
}
sum+=(t[s.size()]);
ch=(char)(sum);
return ch;
}
};
第二个思路是这篇文章里的Hash表的思路,但我个人感觉过于复杂,事实上这个思路的runtime表现也很不好。
第三个思路依然是上篇文章里的,基本想法是位运算思路,这个思路runtime跟第一个思路表现差不多,都是可以考虑的思路。