力扣389-找不同

一、原题题目

1.1 题目

给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

1.2 示例

示例一

输入： s = “abcd”, t = “abcde”

输出： “e”

解释： ‘e’ 是那个被添加的字母。
示例二

输入： s = “”, t = “y”

输出： “y”
示例三

输入： s = “a”, t = “aa”

输出： “a”
示例四

输入： s = “ae”, t = “aea”

输出： “a”

提示：

0 <= s.length <= 1000
t.length == s.length + 1
s 和 t 只包含小写字母

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-difference/

二、解题思路1

2.1 题目理解分析

题目很直白，也非常容易想到思路，我第一个思路就是用一个 HashMap 去存储 s 字符串中每个字符的个数（字符作为 key ，个数作为 value）。然后遍历 t 字符串的时候去减掉对应字符的个数值，当有不在 HashMap 中的字符或个数已经为0的字符即为加进去的字符。

2.2 详细代码（Java）

public class Solution {
  public char findTheDifference(String s, String t) {
    HashMap<Character,Integer> map = new HashMap<>();   // 定义 map 
    for (int i = 0;i<s.length();i++){                   // 统计 s 中的每个字符个数
      char ch = s.charAt(i);
      map.put(ch,map.containsKey(ch)?map.get(ch)+1:1);
    }
    for (int i = 0;i<t.length();i++){                   // 检验 t 中添加进去的字符
      char ch = t.charAt(i);
      if (map.containsKey(ch)&&map.get(ch)>0) 
        map.put(ch,map.get(ch)-1);                  // 如果字符在 map 中存在，并且个数大于0，则个数减一
      else return ch;                                 // 否则为添加进去的那个字符，直接返回
    }
    return ' ';
  }
}

2.3 算法执行结果

算法简单是简单，结果也很残忍，时间上只击败8.17%的用户，不行~~~还得想想其他思路提升性能。下面是将存储方法改为数组存储，因为题目限制了只有小写字母，所有用26长度的 int 数组就可以达到统计个数的目的。

public class Solution {
  public char findTheDifference(String s, String t) {
    int[] count = new int[26];                   // 定义数组存储个数
    for (int i = 0;i<s.length();i++){            // 同时对 s 和 t 中字符个数统计
      count[s.charAt(i)-'a']++;                // s 中的字符相应位置加1
      count[t.charAt(i)-'a']--;                // t 中的字符相应位置减1
    }
    count[t.charAt(t.length()-1)-'a']--;        // t 中最后一个字符相应位置减1
    for (int i = 0;i<26;i++){                   // 查找添加的字符
      if (count[i]==-1)
        return (char)(i+'a');               // 个数为-1的即为添加的字符，其他都是0
    }
    return ' ';
  }
}

速度上得到了不小的提升，不过还不是很理想。再去参考参考别的大神的题解看看…….

三、解题思路2(位运算)

3.1 题目理解分析

这题说的是字符串 t 只比 s 多了一个字符，其他字符他们的数量都是一样的，如果我们把字符串 s 和 t 合并就会发现，除了那个多出的字符出现奇数次，其他的所有字符都是出现偶数次，这种情况我们就可以用异或运算来解决啦。

异或运算的三点规律：

1.a^a=0：任何数字和自己异或都是0

2.a^0=a：任何数字和0异或还是自己

3.a^b^a=a^a^b：异或运算具有交换律
用题目示例一举例

s = “abcd”，t = “abcde”，合并之后为 “abcdabcde” ，每一位都进行异或运算为 a^b^c^d^a^b^c^d^e ，再利用上述规律3 可以交换为 a^a^b^b^c^c^d^d^e ，再用规律1可以得到 0^0^0^0^e ，最后由规律2得到最后结果为 e。

3.2 详细代码（Java）

public class Solution {
  public char findTheDifference(String s, String t) {
    char[] chars = s.concat(t).toCharArray();   // 合并 s 和 t 并且转化为 char 数组
    char result = 0;                            // 定义输出结果的字符
    for (char aChar : chars) {
      result ^= aChar;                        // 对每一个字符进行异或操作
    }
    return result;                              // 返回保留结果的字符
  }
}