问题描述:
You are given two strings s and t.
String t is generated by random shuffling string s and then add one more letter at a random position.
Return the letter that was added to t.
字符串t是字符串s的字符外加一个随机字符的乱序,找到这个随机字符
思路:
可以用哈希表追踪字符的增减变化,也可以把字符当成数字,通过两个字符串各自加和(sum1,sum2),找出sum2-sum1,就是多出来的字符对应的ascii码
提示:在JAVA中,int sum=0; sum=sum+‘a’, sum的值就是a对应的ascii码97,转换回来时,要显式声明,char ch=(char) sum;
我这里采用的是哈希表的方法:
代码如下:
class Solution {
public char findTheDifference(String s, String t) {
Map<Character, Integer> map=new HashMap<>();
int i=0;
while(i<s.length()){
if(!map.containsKey(s.charAt(i))){
map.put(s.charAt(i), 1);
}
else{
map.replace(s.charAt(i),map.get(s.charAt(i))+1);
}
i++;
}
i=0;
while(i<t.length()){
if(!map.containsKey(t.charAt(i))){
return t.charAt(i);
}
else if(map.get(t.charAt(i))==0){
return t.charAt(i);
}
else{
map.replace(t.charAt(i), map.get(t.charAt(i))-1);
}
i++;
}
return ' ';
}
}
时间复杂度:O(n)