Find the Difference

Posted on Edited on In Views:

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:

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

Example 2:

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

哈希表：

时间复杂度：O(n)

空间复杂度：O(S)，S表示字符集大小。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char,int> set;
        for (char ch : s)set[ch]++;
        for (char ch : t) {
            if (set[ch])set[ch]--;
            else return ch;
        }
        return ' ';
    }
};

求和：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int as = 0, at = 0;
        for (char ch: s) {
            as += ch;
        }
        for (char ch: t) {
            at += ch;
        }
        return at - as;
    }
};

位运算：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char findTheDifference(string s, string t) {
        int ret = 0;
        for (char ch: s) {
            ret ^= ch;
        }
        for (char ch: t) {
            ret ^= ch;
        }
        return ret;
    }
};