一、题目
函数原型：char findTheDifference(char * s, char * t)
二、思路
作者原先的思路是先将两个字符串从小到大排序，然后两个字符串依次比较。若出现字符串t中的元素和字符串s不相等，则说明该元素就是被添加的字母。
但是，该算法时间上仅仅击败13.33%的人，效率极低。
int cmp(const void *e1,const void *e2) { return *(char*)e1 - *(char*)e2; } char findTheDifference(char * s, char * t){ int sz1=strlen(s); int sz2=strlen(t); qsort(s,sz1,1,cmp); qsort(t,sz2,1,cmp); int i=0; for(i=0;i<sz1;i++) { if(s[i]!=t[i]&&s[i]==t[i+1]) { return t[i]; } } return t[i]; }
下面介绍几种时间效率比较高的算法：
思路1：
利用找单身狗的思想，详见：《leetcode：136. 只出现一次的数字（找单身狗）》
将两个字符串全部进行异或运算，最后得到的就是只出现一次的字母，即被添加的字母
char findTheDifference(char* s, char* t) { char result=0; int sz1=strlen(s); int sz2=strlen(t); for(int i=0;i<sz1;i++) { result^=s[i]; } for(int i=0;i<sz2;i++) { result^=t[i]; } return result; }
思路2：
用字符串t的字母总和减去字符串s的字母总和，因为相同字母相减结果为0，所以剩下的就是被添加的字母
char findTheDifference(char* s, char* t) { char result=0; int sz1=strlen(s); int sz2=strlen(t); for(int i=0;i<sz2;i++) { result+=t[i]; } for(int i=0;i<sz1;i++) { result-=s[i]; } return result; }
思路3：
设置一个大小为26的数组（初始值为0），字母 a-z 分别对应位置 0-25 ，通过各字母通过减去a可以转换为对应的数字。先遍历字符串s，当某个字母出现其对应的位置就+1；再遍历字符串t，当某个字母出现其对应位置就-1。最后若某个位置变为了-1，说明该字母在s中未出现，在t中出现了，该字母就是被添加的字母，返回该字母即可。
char findTheDifference(char* s, char* t) { int nums[26]={0}; memset(nums,0,sizeof(nums)); int sz1=strlen(s); int sz2=strlen(t); for(int i=0;i<sz1;i++) { nums[s[i]-'a']++; } for(int i=0;i<sz2;i++) { nums[t[i]-'a']--; if(nums[t[i]-'a']==-1) return t[i]; } return ' '; }
