389. Find the Difference

  • 51.3%

https://leetcode.com/problems/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.

1
2
3
4
5
6
7
8
9
10
11
12
> Example:
>
> Input:
> s = "abcd"
> t = "abcde"
>
> Output:
> e
>
> Explanation:
> 'e' is the letter that was added.
>

java

https://discuss.leetcode.com/topic/55912/java-solution-using-bit-manipulation

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

maybe a more elegant version:

1
2
3
4
5
6
7
8
9
public char findTheDifference(String s, String t) {
int n = t.length();
char c = t.charAt(n - 1);
for (int i = 0; i < n - 1; ++i) {
c ^= s.charAt(i);
c ^= t.charAt(i);
}
return c;
}

https://discuss.leetcode.com/topic/56050/simple-java-8ms-solution-4-lines

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public char findTheDifference(String s, String t) {
// Initialize variables to store sum of ASCII codes for
// each string
int charCodeS = 0, charCodeT = 0;
// Iterate through both strings and char codes
for (int i = 0; i < s.length(); ++i) charCodeS += (int)s.charAt(i);
for (int i = 0; i < t.length(); ++i) charCodeT += (int)t.charAt(i);
// Return the difference between 2 strings as char
return (char)(charCodeT - charCodeS);
}
}

cpp

https://discuss.leetcode.com/topic/55940/concise-c-solution-using-xor

It is the same idea with 136. Single Number (https://leetcode.com/problems/single-number/)

1
2
3
4
5
6
7
8
9
class Solution {
public:
char findTheDifference(string s, string t) {
char r=0;
for(char c:s) r ^=c;
for(char c:t) r ^=c;
return r;
}
};

my code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
char findTheDifference(string s, string t) {
int res = 0;
for(auto num:s)
res ^= int(num);
for(auto num:t)
res ^= int(num);
return char(res);
}
};

python

https://discuss.leetcode.com/topic/55918/1-liners-and-2-liner-in-python

Using XOR:

1
2
3
class Solution(object):
def findTheDifference(self, s, t):
return chr(reduce(operator.xor, map(ord, s + t)))

Using collections.Counter():

1
2
3
class Solution(object):
def findTheDifference(self, s, t):
return list((collections.Counter(t) - collections.Counter(s)))[0]

A 2-liner here using sorted():

1
2
3
4
class Solution(object):
def findTheDifference(self, s, t):
s, t = sorted(s), sorted(t)
return t[-1] if s == t[:-1] else [x[1] for x in zip(s, t) if x[0] != x[1]][0]

A few one-liners using sorted():

1
2
3
4
return next((c for c, d in zip(sorted(t), sorted(s)) if c != d), max(t))
return next(c for c, d in zip(sorted(t), sorted(s) + [None]) if c != d)
return next(c for c, d in map(None, sorted(t), sorted(s)) if c != d)
return filter(None, map(lambda c, d: c != d and c, sorted(t), sorted(s)))[0]

谢谢你,可爱的朋友。