【leetcode】389 Find the Difference

发表于 | 分类于 ，

找出两个字符串的不同之处


描述

给定一个字符串 s , 构造一个字符串 t，t 为 s 的一个排列，然后随机的在 t 的任 1 位置添加一个任意字符，要求需要找出这个字符。

样例

1
2
输入: s = "abc" t = "abck"
输出: k

思路

统计每个字符出现的次数，比较 s 和 t 的统计结果，发现不同则可以返回这个字符。另一种方案是将t 字符串所有的字符加起来，然后减去 s 字符串的累加结果，得到的差值便是这个差异字符的 ASCLL 码，当然这一步也可以利用异或来完成。

代码

1
2
3
4
5
6
7
8
9
class Solution {
public:
    char findTheDifference(string s, string t) {
        int maxval = 0;
        for (int i = 0; i <t.size(); i++) { maxval += t[i]; }
        for (int i = 0; i <s.size(); i++) { maxval -= s[i]; }
        return maxval ;
    }
};

统计次数的代码：

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) {
        unordered_map<char, int> m;
        for (auto c : s) { m[c]++; }
        char res;
        for (auto c : t) {
            if (m[c] <= 0) {
                res = c;
                break;
            }
            else {
                m[c]--;
            }
        }
        return res;
    }
};

参考

原题链接