时间戳

首页 > 解决方案 > 在不到一秒的时间内执行一个字谜检查器算法

python - 在不到一秒的时间内执行一个字谜检查器算法

问题描述

我创建了这个算法来检查两个字符串是否是彼此的字谜。在本练习中，如果两个字符串具有相同的字符或仅相差一个，我认为它们是彼此的字谜。例如，数学和数学是字谜，但即使是数学和数学也是字谜。我需要在不到一秒的时间内执行这个算法，但是测试中包含一些示例，有时需要超过 10 分钟。很明显，这可以做得更好。嵌套的 for 循环是问题所在，但如果没有它，我就无法想出一个可能的解决方案。

#len(word1) <= len(word2)
def check(word1, word2): 
   lword1 = len(word1)
   lword2 = len(word2)
   sword1 = sorted(word1)
   sword2 = sorted(word2)

   # lword1 == lword2
   if lword1 == lword2: 
       return sword1 == sword2

   # lword1 < lword2, word2 has one more character
   sword2_copy = sword2.copy()
   for c in sword2:
       if c in sword1:
           sword1.remove(c)
           sword2_copy.remove(c)

   return len(sword1) == 0 and len(sword2_copy) == 1


def main(fin, fout, k):

   words = [line.rstrip('\n') for line in open(fin)] 
   words = [x.strip(' ') for x in words]

   d = {}

   for w1 in words:
       for w2 in words:
           if len(w1) == len(w2) or len(w1) == len(w2) - 1:
               if check(w1, w2):
                   if w1 not in d.keys():
                       d[w1] = [w2]
                   else:
                       d[w1].append(w2)

   highV = list(d.values())[0]
   highK = list(d.keys())[0]
   for key, value in d.items():
       if len(value) > len(highV) or (len(value) == len(highV) and key < highK):
           highK = key
           highV = value

   highV.sort()

   with open(fout, 'w') as f:
       for i in range(len(highV)):
           f.write(highV[i]+' ')
           if (i + 1) % k == 0: 
               f.write('\n')

   return int(len(highV))

标签： pythonpython-3.xanagram

解决方案

您应该从集合中查看计数器：

from collections import Counter
str = 'Testanagram'
counter = Counter(str)
print(counter)
> Counter({'a': 3, 'T': 1, 'e': 1, 's': 1, 't': 1, 'n': 1, 'g': 1, 'r': 1, 'm': 1})

使用这个，你应该更快 - 你也可以从另一个计数器中减去一个计数器来获得差异

推荐阅读