389. Find the Difference

发表于 | 分类于 | 浏览 次

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:

1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

AC代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    char findTheDifference(string s, string t) {
        map<char, int> mp;
        for(auto c:s){
            mp[c] = mp.find(c) == mp.end() ? 1 : mp[c] + 1;
        }
        char res;
        for(auto c:t){
            if(mp.find(c) == mp.end() || mp[c] == 0){
                res = c;
                break;
            }
            mp[c]--;
        }
        return res;
    }
};

思路：首先统计源字符串s中的每一个字符及其出现次数，然后统计打乱了顺序并加入了新字符的字符串t中每个字符的出现次数。新加入的字符要么是源字符串中不存在的字符，要么比源字符串中的出现次数加1。
时间复杂度为O(n)，空间复杂度为O(n)。