## Sunday, August 28, 2016

### 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.```

``````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:
``````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/67128/java-5-ms-beats-98-12
- maybe overflow
``````    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);
}``````

``````        for (int i = 0; i < 26; i++) alpha[i] = 0;
for (char c : s.toCharArray())
alpha[ c - 'a' ]++;

for (char c : t.toCharArray()) {
//could do decrement first, then check but yeah
if (--alpha[c - 'a'] < 0)
return c;
}

return 0;``````

def findTheDifference(self, s, t): """ :type s: str :type t: str :rtype: str """ ds = collections.Counter(s) dt = collections.Counter(t) return (dt - ds).keys().pop()

https://segmentfault.com/a/1190000006739199
``````    public char findTheDifference(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
char[] schar = s.toCharArray();
char[] tchar = t.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(schar[i])) map.put(schar[i], map.get(schar[i])+1);
else map.put(schar[i], 1);
}
for (int i = 0; i < t.length(); i++) {
if (map.containsKey(tchar[i]) && map.get(tchar[i]) > 0) map.put(tchar[i], map.get(tchar[i])-1);
else return tchar[i];
}
return 'a';
}``````