389. Find the Difference

Question

You are given two strings s and t.

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

Return the letter that was added to t.

Algorithm

1. This question can be solved intuitively. We turn the strings to arrays, sort the arrays and compare each character to find the first non equal one. Or all the chars in s are equal to the previous chars in t, the newly added char would be the last one in t. Implementation as code1. Thus the tine complicity is O(nlogn) due to the sorting. And space complexity is O(n) because of the space used for characters array.

2. Well this question can be solved using bit manipulation. Since we only have one character difference, we could apply XOR(^) to for each character, the result for same character is 0, so the only thing left in the end would be the extra added one. The time complexity can be optimized to O(n) since we only traverse the strings at once at the same time. And space takes O(1).

   Actually the charAt() takes O(1). From the java source code:

   public char charAt(int index) { if ((index < 0) || (index >= value.length)) { throw new StringIndexOutOfBoundsException(index); } return value[index]; }

Code

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

Optimized

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