Codewars Scramblies问题：Python代码性能过慢求助

性能问题根源 #

1. 不可变字符串的频繁拷贝：Python字符串是不可变对象，每次replace操作都会创建新的字符串实例。处理长字符串时，反复的内存分配和拷贝会极大消耗时间。
2. 低效的字符查找与修改：find和replace都是线性扫描操作，每次循环都要遍历字符串，整体时间复杂度达到O(len(s2)*len(s1))，在大输入规模下（比如s1、s2长度上万），这种复杂度会直接导致超时。

优化方案：基于字符计数的统计法 #

核心思路是统计两个字符串中每个字符的出现次数，逐一验证s2中每个字符的计数是否都不超过s1中的对应计数。这种方法的时间复杂度为O(len(s1)+len(s2))，效率提升显著。

实现方式1：使用Python内置collections.Counter #

Counter是标准库中专门用于计数的工具，能快速统计字符频率：

from collections import Counter

def scramble(s1, s2):
    count_s1 = Counter(s1)
    count_s2 = Counter(s2)
    for char, cnt in count_s2.items():
        if count_s1.get(char, 0) < cnt:
            return False
    return True

更简洁的写法：

from collections import Counter

def scramble(s1, s2):
    return not (Counter(s2) - Counter(s1))

解释：Counter(s2) - Counter(s1)会返回s2中存在但s1计数不足的字符，若结果为空，则说明s1包含s2所有字符的足够数量。

实现方式2：手动计数（无额外依赖） #

如果不想依赖collections，可以用字典手动统计：

def scramble(s1, s2):
    char_count = {}
    # 统计s1的字符频率
    for char in s1:
        char_count[char] = char_count.get(char, 0) + 1
    # 遍历s2验证计数
    for char in s2:
        if char_count.get(char, 0) == 0:
            return False
        char_count[char] -= 1
    return True

该方法同样是O(m+n)的时间复杂度，且无需导入库，适合对依赖有要求的场景。

测试验证 #

用题目示例测试：

• scramble('rkqodlw', 'world') → 返回True
• scramble('cedewaraaossoqqyt', 'codewars') → 返回True
• scramble('katas', 'steak') → 返回False
  所有示例均能正确输出，且大规模输入下性能远优于原代码。

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