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.
本题最直观的思路为排序后对s和t逐位进行比较。故得以下代码：
class Solution
{
public:
char findTheDifference(string s, string t)
{
sort(s.begin(), s.end());
sort(t.begin(), t.end());
for(int i = ; i < s.size(); i++)
{
if(s[i] == t[i])
{
continue;
}
else
{
return t[i];
}
}
return t[t.size() - ];
}
};
由于排序复杂度过高，于是查询别的解法发现，可以建立一个字母表，s出现一次字母表对应位置+1，t中出现一次对应位置-1。那么只在t中出现的字母的位置为-1。代码如下：
public char findTheDifference(String s, String t) {
if(s == null || s.length() == )
return t.charAt();
int[] letters = new int[];
for(int i = ; i < s.length(); i++){
int sPosition = s.charAt(i) - 'a';
int tPosition = t.charAt(i) - 'a';
letters[sPosition]++;
letters[tPosition]--;
}
int tPosition = t.charAt(t.length()-) - 'a';
letters[tPosition]--;
char res = 'a';
for(int i = ; i < letters.length; i++){
if(letters[i] == -){
res+= i;
break;
}
}
return res;
}