389 Find the Difference¶

Problem:¶

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.

Solutions:¶

public class Solution {
    public char findTheDifference(String s, String t) {
        HashMap<Character, Integer> chars = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            if (!chars.containsKey(c)) {
                chars.put(c, 0);
            }
            chars.put(c, chars.get(c) + 1);
        }
        for (int i = 0; i < t.length(); i ++) {
            char c = t.charAt(i);
            if (!chars.containsKey(c)) {
                return c;
            }
            if (chars.get(c) == 0) {
                return c;
            }
            chars.put(c, chars.get(c) - 1);
        }
        return ' ';
    }
}

public class Solution {
    public char findTheDifference(String s, String t) {
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        Arrays.sort(sc);
        Arrays.sort(tc);
        for (int i = 0; i < sc.length; i ++) {
            if (sc[i] != tc[i]) {
                return tc[i];
            }
        }
        return tc[tc.length - 1];
    }
}

public class Solution {
    public char findTheDifference(String s, String t) {
        int res = 0;
        for (int i = 0; i < s.length(); i ++) {
            res = res^s.charAt(i);
            res = res^t.charAt(i);
        }
        res = res^t.charAt(t.length() - 1);
        return (char)res;
    }
}

public class Solution {
    public char findTheDifference(String s, String t) {
        int res = 0;
        for (int i = 0; i < s.length(); i ++) {
            res = res - s.charAt(i);
            res = res + t.charAt(i);
        }
        res = res + t.charAt(t.length() - 1);
        return (char)res;
    }
}