LeetCode 389题：哈希表解法错误排查求助

问题描述 #

给定两个字符串s和t，t由s随机洗牌后添加一个字符得到，返回新增的字符。约束条件：0 <= s.length <= 1000。

我的实现代码 #

var findTheDifference = function (s, t) {
    let mapSet = {}
    let final = ""

    s.split('').forEach((elem) => {
        mapSet[elem] === undefined ? mapSet[elem] = 1 : mapSet[elem]++
    })

    t.split('').forEach((elem) => {
        mapSet[elem] === undefined ? mapSet[elem] = 1 : mapSet[elem]--

        if (mapSet[elem] != 0) {
            final = elem
        }
    })

    return final
};

出错测试用例 #

• 输入s："ymbgaraibkfmvocpizdydugvalagaivdbfsfbepeyccqfepzvtpyxtbadkhmwmoswrcxnargtlswqemafandgkmydtimuzvjwxvlfwlhvkrgcsithaqlcvrihrwqkpjdhgfgreqoxzfvhjzojhghfwbvpfzectwwhexthbsndovxejsntmjihchaotbgcysfdaojkjldprwyrnischrgmtvjcorypvopfmegizfkvudubnejzfqffvgdoxohuinkyygbdzmshvyqyhsozwvlhevfepdvafgkqpkmcsikfyxczcovrmwqxxbnhfzcjjcpgzjjfateajnnvlbwhyppdleahgaypxidkpwmfqwqyofwdqgxhjaxvyrzupfwesmxbjszolgwqvfiozofncbohduqgiswuiyddmwlwubetyaummenkdfptjczxemryuotrrymrfdxtrebpbjtpnuhsbnovhectpjhfhahbqrfbyxggobsweefcwxpqsspyssrmdhuelkkvyjxswjwofngpwfxvknkjviiavorwyfzlnktmfwxkvwkrwdcxjfzikdyswsuxegmhtnxjraqrdchaauazfhtklxsksbhwgjphgbasfnlwqwukprgvihntsyymdrfovaszjywuqygpvjtvlsvvqbvzsmgweiayhlubnbsitvfxawhfmfiatxvqrcwjshvovxknnxnyyfexqycrlyksderlqarqhkxyaqwlwoqcribumrqjtelhwdvaiysgjlvksrfvjlcaiwrirtkkxbwgicyhvakxgdjwnwmubkiazdjkfmotglclqndqjxethoutvjchjbkoasnnfbgrnycucfpeovruguzumgmgddqwjgdvaujhyqsqtoexmnfuluaqbxoofvotvfoiexbnprrxptchmlctzgqtkivsilwgwgvpidpvasurraqfkcmxhdapjrlrnkbklwkrvoaziznlpor"
• 输入t："qhxepbshlrhoecdaodgpousbzfcqjxulatciapuftffahhlmxbufgjuxstfjvljybfxnenlacmjqoymvamphpxnolwijwcecgwbcjhgdybfffwoygikvoecdggplfohemfypxfsvdrseyhmvkoovxhdvoavsqqbrsqrkqhbtmgwaurgisloqjixfwfvwtszcxwktkwesaxsmhsvlitegrlzkvfqoiiwxbzskzoewbkxtphapavbyvhzvgrrfriddnsrftfowhdanvhjvurhljmpxvpddxmzfgwwpkjrfgqptrmumoemhfpojnxzwlrxkcafvbhlwrapubhveattfifsmiounhqusvhywnxhwrgamgnesxmzliyzisqrwvkiyderyotxhwspqrrkeczjysfujvovsfcfouykcqyjoobfdgnlswfzjmyucaxuaslzwfnetekymrwbvponiaojdqnbmboldvvitamntwnyaeppjaohwkrisrlrgwcjqqgxeqerjrbapfzurcwxhcwzugcgnirkkrxdthtbmdqgvqxilllrsbwjhwqszrjtzyetwubdrlyakzxcveufvhqugyawvkivwonvmrgnchkzdysngqdibhkyboyftxcvvjoggecjsajbuqkjjxfvynrjsnvtfvgpgveycxidhhfauvjovmnbqgoxsafknluyimkczykwdgvqwlvvgdmufxdypwnajkncoynqticfetcdafvtqszuwfmrdggifokwmkgzuxnhncmnsstffqpqbplypapctctfhqpihavligbrutxmmygiyaklqtakdidvnvrjfteazeqmbgklrgrorudayokxptswwkcircwuhcavhdparjfkjypkyxhbgwxbkvpvrtzjaetahmxevmkhdfyidhrdeejapfbafwmdqjqszwnwzgclitdhlnkaiyldwkwwzvhyorgbysyjbxsspnjdewjxbhpsvj"
• 实际输出："j"
• 预期输出："t"

错误原因分析 #

你的代码逻辑存在两个关键问题：

1. 结果被后续字符覆盖：遍历t时，只要字符计数不等于0就更新final变量。新增字符被识别后，后续处理其他字符时，若该字符的计数因s和t的次数差变为非0值（比如s中某字符出现2次，t中出现1次，减1后计数为1），会覆盖之前正确的final值，最终返回最后一个导致计数非0的字符，而非真正新增的字符。
2. 字符计数处理逻辑错误：当t中出现s没有的字符时，你将其计数设为1，而不是直接标记为新增字符。这种处理方式会让该字符的计数处于非0状态，但后续其他字符的处理仍可能覆盖结果。

修正后的代码 #

哈希表修正版 #

var findTheDifference = function (s, t) {
    const map = {};
    // 统计s中各字符出现次数
    for (const c of s) {
        map[c] = (map[c] || 0) + 1;
    }
    // 遍历t，逐个减少计数，找到计数异常的字符
    for (const c of t) {
        if (!map[c]) { // 该字符不在s中，直接返回
            return c;
        }
        map[c]--;
        if (map[c] < 0) { // 计数为负，说明t中该字符比s多一个
            return c;
        }
    }
    // 理论上不会走到这里，因为t比s长一个字符
    return '';
};

更简洁的ASCII求和版 #

var findTheDifference = function (s, t) {
    let sum = 0;
    for (const c of t) sum += c.charCodeAt(0);
    for (const c of s) sum -= c.charCodeAt(0);
    return String.fromCharCode(sum);
};

内容的提问来源于stack exchange，提问作者Abhishek Sah