导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二
    3. 方法三
    4. 方法四

LeetCode-389.Find the Difference

题目

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t .

Example:

Input:
s = “abcd”
t = “abcde”

Output:
e

Explanation:
‘e’ is the letter that was added.

翻译

给出两个由小写字母组成的字符串,s和t。
字符串t是由字符串s经过随机整理后,在一个随机位置增加一个字母生成的。
找出t中增加的字母。
例如:
输入:s = “abcd”,t = “abcde”
输出:e
解释:字母’e’是增加的

方法一

第一想法便是利用加减,将t所有字母的和,减去s所有字母的和,即为所求:

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public char findTheDifference(String s, String t) {
char sum = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
sum += t.charAt(i);
sum -= s.charAt(i);
}
sum += t.charAt(len);
return sum;
}
}

Runtime: 7 ms

方法二

类似136. Single Number,将方法一改为采用异或:

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public char findTheDifference(String s, String t) {
char sum = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
sum ^= t.charAt(i);
sum ^= s.charAt(i);
}
sum ^= t.charAt(len);
return sum;
}
}

Runtime: 7 ms

方法三

记录一个Map,将s中所有字母放入,并记录出现次数,然后遍历t,减去相应字母,当出现-1次的字母便是所求:

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public char findTheDifference(String s, String t) {
Map<Character, Integer> chars = new HashMap<Character, Integer>();
for (char c : s.toCharArray())
chars.put(c, chars.get(c) == null ? 1 : chars.get(c) + 1);
for (char c : t.toCharArray()) {
if (chars.get(c) == null || chars.get(c) == 0) return c;
chars.put(c, chars.get(c) - 1);
}
return ' ';
}
}

Runtime: Time Limit Exceeded

方法四

因为都是小写字母,所以可以用一个长度为26的数组来代替方法三中的map,记录每个字母出现次数:

1
2
3
4
5
6
7
8
public class Solution {
public char findTheDifference(String s, String t) {
int[] chars = new int[26];
for (char c : s.toCharArray()) chars[c - 'a']++;
for (char c : t.toCharArray()) if (--chars[c - 'a'] == -1) return c;
return ' ';
}
}

Runtime: 8 ms

参考:
http://www.cnblogs.com/grandyang/p/5816418.html