find-the-difference

Find the Difference – LeetCode 389

Problem

Description

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.

Answer

Original

Code

class Solution {
public:
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        for(unsigned i = 0; i != s.size(); ++i)
            if(s[i] != t[i]) return t[i];
        return t[s.size()];
    }
};

思路

老思路。时间复杂度$O(nlog{n})$，空间复杂度$O(1)$。
耗时$7$ ms，排名$86.11\%$

Better

思路

使用异或。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$5$ ms，排名$44.02\%$

Code

class Solution {
public:
    char findTheDifference(string s, string t) {
        int map[26] = {0};
        for(char &c : s)
            ++map[c - 'a'];
        for(char &c : t)
            if(!(map[c - 'a']--)) return c;
    }
};