Find the Difference

题目链接

传送门

题目大意

给定两个字符串S和T,T是在S的基础上增加一个字符构成的字符串,找出T中那个增加的字符。

解题思路

给出两个测试样例

  • S = “abcd”,T = “abcda”

  • S = “abcd”,T = “abcde”

构造一个字符到整数的映射,即map<char, int>。
初始化是遍历T(因为T中的字符集是二者的并集),每个字符对应的值+1;
接下来遍历S,每个字符的map计数-1;
以上两个操作执行后,剩下map计数不为0的,即为所求字符。
时间复杂度O(n),空间复杂度O(n)。

参考代码

class Solution {
public:
    char findTheDifference(string s, string t) {
        int lengthS = s.length();
        int lengthT = t.length();
        map<char, int> mapS;
        // 初始化
        for (int index = 0; index < lengthT; index ++) {
            mapS[t[index]] = 0;
        }
        for (int index = 0; index < lengthT; index ++) {
            mapS[t[index]] ++;
        }
        // 遍历S
        for (int index = 0; index < lengthS; index ++) {
            mapS[s[index]] --;
        }
        // 遍历T
        for (int index = 0; index < lengthT; index ++) {
            if (0 < mapS[t[index]]) {
                return t[index];
            }
        }
    }
};

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图