如何优化LeetCode找不同字符问题的代码内存占用？

问题描述 #

给定两个字符串s和t，t由s随机打乱后添加一个随机字符生成，需返回t中新增的字符。

你的Python解决方案 #

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        
        dict_s = {}
        dict_t = {}

        # loop through string and add the frequency into a dictionary
        for i in s:
            if i not in dict_s:
                dict_s[i] = 1
            else:
                dict_s[i] += 1

        for i in t:
            if i not in dict_t:
                dict_t[i] = 1

            else:
                dict_t[i] += 1

        # compare the frequency of both dictionaries
        for key, value in dict_t.items():
            if key not in dict_s:
                difference = key

            elif value != dict_s[key]:
                difference = key

        return difference

关于内存问题的分析 #

你的代码目前的内存占用和运行时间在LeetCode测试用例下是合理的，而且不存在会在大规模项目中引发严重内存问题的明显不良写法——因为字典的键数量受字符集限制（比如题目限定小写字母的话最多26个键），不会随着字符串长度增长线性膨胀，内存开销始终是常数级的。

不过代码可以从简洁性和内存效率上优化：

• 不需要维护两个独立字典，只用一个字典统计字符频率即可：先统计s中每个字符的出现次数，再遍历t逐个减少计数，当某个字符计数变为负数时，它就是新增字符。
• 手动判断字符是否在字典里的逻辑可以用collections.defaultdict或者dict.get()简化，减少重复代码。
• 更极致的优化是用ASCII码求和：计算s所有字符的ASCII值总和，再计算t的总和，两者差值对应的字符就是答案，这种方法内存复杂度为O(1)，仅需几个变量。

优化后的示例代码 #

方法1：单字典统计 #

from collections import defaultdict

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        char_count = defaultdict(int)
        for c in s:
            char_count[c] += 1
        
        for c in t:
            char_count[c] -= 1
            if char_count[c] < 0:
                return c
        
        # 题目保证存在新增字符，此处不会执行到
        return ""

方法2：ASCII求和法（最优内存） #

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        total_s = sum(ord(c) for c in s)
        total_t = sum(ord(c) for c in t)
        return chr(total_t - total_s)

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