LeetCode 389 - Find the Difference

http://bookshadow.com/weblog/2016/08/28/leetcode-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.

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

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;
}

X. https://discuss.leetcode.com/topic/56050/simple-java-8ms-solution-4-lines
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);
    }

X. https://discuss.leetcode.com/topic/55938/java-solution-using-array-6ms

        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;

分别统计s与t的字母个数，然后比对即可
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';
    }