这是悦乐书的第214次更新，第227篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第82题（顺位题号是389）。给定两个字符串s和t，它们只包含小写字母。字符串t由随机混洗字符串s生成，然后在随机位置再添加一个字母。找到t中添加的字母。例如：
输入：s =“abcd”, t =“abcde”
输出：'e'
说明：'e'是添加的字母。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
因为限定字符串都是小写字母，可以借助一个26长度的数组，将t中的字符出现次数记录下来，然后再去遍历s的字符，只要有对应的就做减法，最后再去找数组中为1的元素的索引，将其和字符a相加，就是t中添加的字母。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public char findTheDifference(String s, String t) {
int[] arr = new int[26];
for (int i=0; i<t.length(); i++) {
arr[t.charAt(i)-'a']++;
}
for (int j=0; j<s.length(); j++) {
arr[s.charAt(j)-'a']--;
}
for (int k=0; k<arr.length; k++) {
if (arr[k] == 1) {
return (char)(k+'a');
}
}
return '0';
}
03 第二种解法
还是使用长度26的数组，将s中出现的字符及次数记录下来，再去遍历t的字符，同时对其对应数组中的元素做自减，如果自减后小于0，即表示当前字符没有在s中出现过，此字符就是t中添加的字母。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public char findTheDifference2(String s, String t) {
int[] arr = new int[26];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)-'a']++;
}
for (int j=0; j<t.length(); j++) {
if (--arr[t.charAt(j)-'a'] < 0) {
return t.charAt(j);
}
}
return '0';
}
04 第三种解法
使用异或位运算，其规则是两边的对应位不同时，取1，否则取0。两个相同的数做异或运算时，运算结果是0。0和一个非0的数做异或运算时，运算结果是那个非0的数。将s和t中的所有字符做异或运算，最后的运算结果就是多出来的那个字符。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public char findTheDifference3(String s, String t) {
int ch = 0;
for (int i=0; i<s.length(); i++) {
ch = ch^s.charAt(i);
}
for (int j=0; j<t.length(); j++) {
ch = ch^t.charAt(j);
}
return (char)ch;
}
05 第四种解法
此解法思路和第三种解法一样，只是将两次循环合并到一次循环中去了。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public char findTheDifference4(String s, String t) {
int ch = t.charAt(t.length()-1);
for (int i=0; i<s.length(); i++) {
ch = ch^t.charAt(i)^s.charAt(i);
}
return (char)ch;
}
06 第五种解法
既然可以做异或运算，那么也可以尝试做加减运算，用t中所有字符的和减去s中所有字符的和，剩下的差就是t中多出的字母。
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
public char findTheDifference5(String s, String t) {
char ch = t.charAt(t.length()-1);
for (int i=0; i<s.length(); i++) {
ch -= s.charAt(i);
ch += t.charAt(i);
}
return ch;
}
07 小结
算法专题目前已连续日更超过两个月，算法题文章82+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
