我试图解决一个问题,其中两个字符串作为参数给出,任务是确定第一个字符串是否包含生成第二个字符串所需的所有元素。我认为我有一个相当简单的解决方案,通过从两个字符串创建字典,其中键是字符串中的字符,值是它们各自的出现次数。代码如下:
def scramble(s1, s2):
s1dict = {x: s1.count(x) for x in s1}
s2dict = {y: s2.count(y) for y in s2}
s3dict = {k:s2dict[k] for k in s2dict and s1dict[k] >= s2dict[k]}
return s3dict == s2dict
当我尝试将解决方案提交到web质询解释器时,它会说我的代码超时了。我知道对于大型字符串,这个解决方案会导致大量的迭代…我可以采取什么方法来提高效率?你知道吗
正如其他人所说,词典理解并不是天生的低效。如果你想加快你的解决方案,你应该看看你的算法。你知道吗
s1dict = {x: s1.count(x) for x in s1}
是获取s1
中所有字符计数的低效方法。如果s1
是长度N,那么它将在s1
中迭代N次,使其成为O(N^2)。如果你要自己实现这个逻辑,它会像这样:有一种方法可以在O(N)时间内得到计数。你知道吗
或者,您可以使用
collections.Counter
为您执行此操作:s1dict = collections.Counter(s1)
。你知道吗你计算s3dict的方法实际上是无效的。我也不认为字典理解是比较这两本字典的最好方法。您可以使用字典理解(
all({k: s1dict.get(k, 0) >= v for k, v in s2dict.items()})
),但为什么不编写一个简单的循环呢?你知道吗相关问题 更多 >
编程相关推荐