如何优化判断字符串所有字符存在于另一字符串的Python函数？

你的这个思路其实是正确的，但在处理较长字符串时，原代码的性能还有优化空间。咱们来拆解一下：

原代码的性能瓶颈 #

你的实现里，每次执行i in tmp和tmp.remove(i)都是O(k)操作（k是当前tmp的长度），所以整体时间复杂度是O(len(str1)*len(str2))。当字符串长度较大时，这种嵌套的线性操作会明显拖慢速度。

更高效的实现方式 #

1. 利用collections.Counter（最简洁高效） #

Python标准库的Counter可以直接统计字符串中每个字符的出现频率，我们只需要验证str1的所有字符频率都不超过str2即可，时间复杂度是O(n + m)（n和m分别是两个字符串的长度）。

代码示例：

from collections import Counter

def almost_anagram(str1, str2):
    count1 = Counter(str1)
    count2 = Counter(str2)
    # 检查str1的每个字符在str2中的数量足够
    for char, cnt in count1.items():
        if count2.get(char, 0) < cnt:
            return False
    return True

甚至可以用更简洁的写法，利用Counter的减法特性：

from collections import Counter

def almost_anagram(str1, str2):
    # Counter减法会保留count1中计数超过count2的字符，若结果为空则符合条件
    return not (Counter(str1) - Counter(str2))

2. 手动统计字符频率（无需依赖标准库） #

如果不能使用collections模块，我们可以自己用字典统计频率，同样能达到O(n + m)的时间复杂度：

def almost_anagram(str1, str2):
    char_count = {}
    # 先统计str2的字符出现次数
    for char in str2:
        char_count[char] = char_count.get(char, 0) + 1
    
    # 遍历str1，逐个扣除计数
    for char in str1:
        # 如果字符不存在或计数已耗尽，直接返回False
        if char_count.get(char, 0) == 0:
            return False
        char_count[char] -= 1
    return True

适用场景对比 #

• 对于短字符串，原代码和优化后的方法差异不大；
• 当字符串长度超过几百甚至上千字符时，O(n + m)的方法会比O(n*m)的原代码快很多，性能差距会随着字符串长度增加而被放大。

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