python - 什么更有效率？使用 .replace() 或将字符串传递给列表

Question

解决以下来自 CodeFights 的问题:

Given two strings, find the number of common characters between them. For s1 = "aabcc" and s2 = "adcaa", the output should be commonCharacterCount(s1, s2) = 3.

Strings have 3 common characters - 2 "a"s and 1 "c".

我处理它的方式是，每当我考虑到一封信时，我都想将其取消，以免再次计算它。我知道 strings 是不可变的，即使使用 .replace() 之类的方法也是如此(replace() 方法返回字符串的副本，实际字符串没有改变)。

为了改变所说的 string，我一开始倾向于做的是简单地将它传递给带有 list(mystring) 的列表，然后改变它。

问题是...以下哪个更有效？考虑到选项 B 一遍又一遍地完成，最坏的情况是字符串相等并且匹配匹配。同时选项 A 出现一次。

选项A)

list(mystring) 

选项 B)

mystring = mystring.replace(letterThatMatches, "")

Answer 1

为找到的每个元素在字符串上调用 replace 的想法根本不是一个好主意:它需要 O(n) 才能做到这一点。如果你对另一个字符串中的每个字符都这样做，它会导致一个 O(m×n) 算法，其中 m 是第一个字符串的字符数，并且n 来自第二个字符串的字符数。

可以简单地使用两个Counter，然后计算两者中的最小值，然后计算计数的总和。喜欢:

from collections import Counter

def common_chars(s1,s2):
    c1 = Counter(s1) # count for every character in s1, the amount
    c2 = Counter(s2) # count for every character in s2, the amount
    c3 = c1 & c2 # produce the minimum of each character
    return sum(c3.values()) # sum up the resulting counts

或者作为单行:

def common_chars(s1,s2):
    return sum((Counter(s1) & Counter(s2)).values())

如果字典查找可以在 O(1) 内完成(这通常适用于一般情况)，这是一个 O(m+n) 算法:然后分别在 O(m) 和 O(n) 中进行计数，并计算不同字符数的最小运行次数(最多为 O( max(m,n))。最后求和又是一个O(max(m,n))操作。

对于样本输入，这导致:

>>> common_chars("aabcc","adcaa")
3