389. Find the Difference

September 03, 2016

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中任意插入一个字母构成的,现在要求我们找出这个加入的字母。

题目要求不高,就是简单的应用哈希表的性质,因为字符集的规模很小,所以我们用一个长度为26的int数组来模拟哈希表即可,代码如下:

/*solution1,use a vector to compute the frequency,4ms*/ 
class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> word(26,0);
        for(int i=0;i<s.size();i++)
            word[s[i]-'a']++;
        for(int i=0;i<t.size();i++){
            int tmp=word[t[i]-'a']--;
            if(tmp==0)
                return t[i];
        }
        return 'a';
    }
};

第一版代码用数组对字符和其出现次数做了一个映射,思路并不复杂。

在查看了讨论区之后,我发现了一个更好的思路,之前我们在解决single number这个问题时,用了位运算的方法,也就是让每个数字相互进行异或XOR运算,最后剩下的一定是出现次数为1的元素,那么这个题实际上也可以让两个字符串中的字符做异或运算,代码如下:

/*solution2,use bit manipulation,4ms*/
class Solution {
public:
    char findTheDifference(string s, string t) {
        char tmp=0;
        for(char a:s)
            tmp^=a;
        for(char b:t)
            tmp^=b;
        return tmp;
    }
};

Stefan大神提出了一行代码解决问题的方案,运用了accumulate方法,思路上和第二种方法相同,代码如下:

/*solution 3,one-line version of solution2*/
class Solution {
public:
    char findTheDifference(string s, string t) {
        return accumulate(begin(s), end(s += t), 0, bit_xor<int>());
    }
};

知识共享许可协议
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017