题目描述
给定两个字符串 $s$ 和 $t$ ,它们只包含小写字母。
字符串 $t$ 由字符串 $s$ 随机重排,然后在随机位置添加一个字母。
请找出在 $t$ 中被添加的字母。
示例 1:
1 2 3
| 输入:s = "abcd", t = "abcde" 输出:"e" 解释:'e' 是那个被添加的字母。
|
示例 2:
1 2
| 输入:s = "", t = "y" 输出:"y"
|
提示:
- $0 <= s.length <= 1000$
- $t.length == s.length + 1$
- $s$ 和 $t$ 只包含小写字母
方法一:哈希表
思路
遍历s
,使用map
记录每个字符出现的次数,然后遍历t
,遍历字符,若在map
中没有出现返回该字符,若出现该字符其出现次数-1,如果出现次数减为0则说明该字符比s
中多,返回该字符。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public char findTheDifference(String s, String t) { Map<Character,Integer> map = new HashMap<>(); for(int i=0;i<s.length();i++){ char ch = s.charAt(i); int cnt = map.containsKey(ch) ? map.get(ch) : 0 ; map.put(ch,++cnt); } for(int i=0;i<t.length();i++){ char ch = t.charAt(i); if(!map.containsKey(ch)){ return ch; } int cnt = map.get(ch); if(cnt==0){ return ch; } map.put(ch,--cnt); } return '0'; } }
|
方法二:ascii码相加
思路
初始化变量sum=0
,遍历s
和t
,将t
中每个字符的ascii码相加,然后将s
中每个字符的ascii码相减,最后返回sum
+t
中最后一个字符的ascii码。
实现
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public char findTheDifference(String s, String t) { char sum=0; for(int i=0;i<t.length();i++){ sum+=t.charAt(i); } for(int i=0;i<s.length();i++){ sum-=s.charAt(i); } return sum; } }
|
方法三:异或
思路
依次遍历s
和t
,将s
和t
中每个字符进行异或,最后返回异或的结果。
因为两个相同的字符异或操作的结果是0,所以最后剩下的字符就是t
中多出来的字符。
实现
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public char findTheDifference(String s, String t) { char sum=0; for(int i=0;i<t.length();i++){ sum^=t.charAt(i); } for(int i=0;i<s.length();i++){ sum^=s.charAt(i); } return sum; } }
|