C++ O(n)


  • 0
    D

    解题报告:

    传送门

    题目大意

    给定两个字符串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];
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.