理解中的两个命令

Question

抱歉，如果标题不准确，但我不确定如何命名，因为我是菜鸟。

我正在尝试解决一个挑战：

"如果 s1 个字符的一部分可以重新排列以匹配 s2，则完成 scramble(str1, str2) 的功能 scramble(str1, str2) True ]，否则 returns False."

所以首先我想这样完成它：

return True if "".join(str(e) for e in s2 if e in s1 and s1.count(e) >= s2.count(e)) == s2 else False

然而，这超时了，显然优化不够。

我没有注意到我认为它与 count() 方法有关所以我试图从下面的 s1 中删除 e 如果 e 是在 s1 - 因为当在 s1 中找到来自 s2 的字符时，它不能再次使用（除非 s1 中存在更多相同的字符）。例如 s2 = 'stress' 需要在 s1 中出现 3 x 's' 次才能实现 return True.

的功能

然而，在下面的代码中，这部分看起来像：s1.replace(e, '', 1) 在我打印 before/after 时没有做任何事情。

def scramble(s1, s2):
    print(s1)
    ("".join(str(e), s1.replace(e, '', 1)) for e in s2 if e in s1)
    print(s1)
scramble('abcdefghijklmnopqrstuvzxy', 'stress')

我能做什么？

Answer 1

您的算法遍历 s2 中的每个字符，然后找到 s1 和 s2 中该字符的字符数。为了便于记号，让m = len(s1)和n = len(s2)。然后，每个 .count() 操作花费的时间与调用 .count() 的字符串中的字符数成线性关系。因此，我们有 O(n) 次迭代，并且每次迭代 O(m + n) 工作——我们的最终运行时间是 O(n*m + n^2)。如果 s2 真的很长，我们会看到很多减速。

我们可以做得更好，方法是在开始分析之前生成计数。

# You can use collections.Counter() here, but I've chosen to forgo this to make the runtime analysis clearer.
def count_characters(s):
    chars = {}
    for char in s:
        if char in chars:
            chars[char] += 1
        else:
            chars[char] = 1
    return chars

def scramble2(s1, s2):
    s1_characters = count_characters(s1)
    s2_characters = count_characters(s2)
   
    for char in s2_characters:
        if char not in s1_characters or s1_characters[char] < s2_characters[char]:
            return False
    
    return True

我们来分析一下修改后的算法的运行时间：

count_characters() 与输入字符串的长度成线性关系。所以字符计数器需要 O(m + n) 时间来生成。然后，我们需要检查 s2_characters 中的每个计数器，并将其与 s1_characters 中的计数器进行比较。无论您是否假设字母表的大小不变，在最坏的情况下这需要 O(n) 时间。因此，最终的运行时间是 O(m + n)——即与输入字符串的长度成线性关系。

理解中的两个命令

two commands in comprehension

python

performance

python-3.x