LeetCode笔记：389. Find the Difference
LeetCode笔记：389. Find the Difference
问题：
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.
大意：
给出两个完全有小写字母组成的字符串s和t。 字符串t是由字符串s打乱顺序后再在随机的位置加上一个字母生成的。 找到添加到t中的那个字母。
思路：
感觉什么都要想到排序，按照字母顺序排序后依次比较过去出现不同数字的就是了，但是排序比较耗时。 于是我思考另一种方法，遍历t中的字母，在s中寻找有没有这个字母，有的话就在s中去掉这一个字母然后继续遍历寻找，如果在s中找不到了，说明就是它了，这样做出来我的实现时间是31ms，但是其实想想这样找跟排序相比时间复杂度好像还是半斤八两，先给出我的代码吧。
代码（Java）：
public class Solution {
public char findTheDifference(String s, String t) {
char key = t.charAt(0);
for (int i = 0; i < t.length(); i++) {
key = t.charAt(i);
if (s.indexOf(key) == -1) return key;
else {
int position = s.indexOf(key);
String before = s.substring(0, position);
String after = s.substring(position+1, s.length());
s = before.concat(after);
}
}
return key;
}
}挺简单的，因为就算s为空字符串，t也一定添加了一个字母，所以这个极端情况在第一行也考虑进去了。然后就是遍历t来在s中寻找了，找到了就从s中去掉继续遍历，值得一提的是这里重新组装s时如果直接用+去组合，也能实现，但是用+拼接字符串会比较耗时。
他山之石
看到了一个8ms的实现方法，代码如下：
public char findTheDifference(String s, String t) {
if(s == null || s.length() == 0)
return t.charAt(0);
int[] letters = new int[26];
for(int i = 0; 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()-1) - 'a';
letters[tPosition]--;
char res = 'a';
for(int i = 0; i < letters.length; i++){
if(letters[i] == -1){
res+= i;
break;
}
}
return res;
}他的做法是，弄一个26位的数字数组，看做是每个位置对应26个字母，然后一位位地遍历s和t中的每个字母，在其字母对应的位置去进行加减操作，s中的字母就加1，t中的字母就减1。因为t只比s多了一个字母，其余都是一样的，所以加加减减最后得到的数字数组一定是一个仅有一个位置的值是-1，其余都是0的数组。那个-1所在的位置对应的字母，就是t中多出的字母了，时间复杂度就是n，确实挺快的。 其实对于这种字母操作的题目，尤其是还特别声明了都是小写字母，就应该条件反射地想到26字母对应26位数字数组的，还是训练不够啊。
还有一种方法，把char字符看成数字，利用相同数字异或等于0的特性，分别遍历两个字符串的字符并全部异或，最后剩下的数字就是那个多出来的数字了，速度更快！
class Solution {
public:
char findTheDifference(string s, string t) {
char r=0;
for(char c:s) r ^=c;
for(char c:t) r ^=c;
return r;
}
};