LeetCode 389. Find the Difference

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.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

---

就还是非常常规的alphabetical string的问题，一下就想到用数组计算count然后++ --看最后< 0的就行。稍微被坑了一小下，count数组的index是char，内容是count。以及要记一下java类型转换的语法是(type)var。

class Solution {
    public char findTheDifference(String s, String t) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            count[c - 'a']--;
        }
        for (int i = 0; i < count.length; i++) {
            if (count[i] < 0) {
                return (char)('a' + i);
            }
        }
        return 0;
    }
}

---

然后看了解答，各路大神各显神通。

可以直接用一个int变量charCode记录两个string的char index之和，s里的charCode--，t里的charCode++，最后相互抵消以后剩下的就是多的。空间复杂度就降到了O(1)。

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

比如也又来了XOR位操作。

class Solution {
    public char findTheDifference(String s, String t) {
        int result = 0;
        for (char c : s.toCharArray()) {
            result ^= c;
        }
        for (char c : t.toCharArray()) {
            result ^= c;
        }
        return (char)result;
    }
}