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:

Input:
s = "abcd"
t = "abcde"

Output:
e

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

 

这道题给了我们两个字符串s和t,t是在s的任意一个地方加上了一个字符,让我们找出新加上的那个字符。这道题确实不是一道难题,首先第一反应的方法就是用哈希表来建立字符和个数之间的映射,如果在遍历t的时候某个映射值小于0了,那么返回该字符即可,参见代码如下:

 

解法一:

class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char, int> m;
        for (char c : s) ++m[c];
        for (char c : t) {
            if (--m[c] < 0) return c;
        }
        return 0;
    }
};

 

我们也可以使用位操作Bit Manipulation来做,利用异或的性质,相同位返回0,这样相同的字符都抵消了,剩下的就是后加的那个字符,参见代码如下:

 

解法二:

class Solution {
public:
    char findTheDifference(string s, string t) {
        char res = 0;
        for (char c : s) res ^= c;
        for (char c : t) res ^= c;
        return res;
    }
};

 

我们也可以直接用加和减,相同的字符一减一加也抵消了,剩下的就是后加的那个字符,参见代码如下:

 

解法三:

class Solution {
public:
    char findTheDifference(string s, string t) {
        char res = 0;
        for (char c : s) res -= c;
        for (char c : t) res += c;
        return res;
    }
};

 

下面这种方法是史蒂芬大神提出来的,利用了STL的accumulate函数,实际上是上面解法二的改写,一行就写完了真是丧心病狂啊,参见代码如下:

 

解法四:

class Solution {
public:
    char findTheDifference(string s, string t) {
        return accumulate(begin(s), end(s += t), 0, bit_xor<int>());
    }
};

 

参考资料:

https://discuss.leetcode.com/topic/55987/java-c-1-liner

https://discuss.leetcode.com/topic/55960/two-java-solutions-using-xor-sum

https://discuss.leetcode.com/topic/55912/java-solution-using-bit-manipulation

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation