Найти группу строк, которые являются анаграммами

Question

Этот вопрос относится к this problem on lintcode. У меня есть рабочее решение, но для огромного теста требуется слишком много времени. Мне интересно, как это можно улучшить? Возможно, я могу уменьшить количество сравнений, которые я делаю во внешнем цикле.

class Solution: 
    # @param strs: A list of strings 
    # @return: A list of strings 
    def anagrams(self, strs): 
     # write your code here 
     ret=set() 
     for i in range(0,len(strs)): 
      for j in range(i+1,len(strs)): 
       if i in ret and j in ret: 
        continue 
       if Solution.isanagram(strs[i],strs[j]): 
        ret.add(i) 
        ret.add(j) 

     return [strs[i] for i in list(ret)] 


    @staticmethod 
    def isanagram(s, t): 
     if len(s)!=len(t): 
      return False 
     chars={} 
     for i in s: 
      if i in chars: 
       chars[i]+=1 
      else: 
       chars[i]=1 

     for i in t: 
      if i not in chars: 
       return False 
      else: 
       chars[i]-=1 
       if chars[i]<0: 
        return False 

     for i in chars: 
      if chars[i]!=0: 
       return False 
     return True 

Update: Просто добавить, не смотря на встроенный вещих решениях, такие как использование Counter, которые уже оптимизированы. Добавили предложения Майка, но все же превышают лимит времени.

Answer 1

Ваше решение медленное, потому что вы не пользуетесь структурами данных python.

Вот решение, которое собирает результаты в Словаре:

class Solution: 
    def anagrams(self, strs): 
     d = {} 
     for word in strs: 
      key = tuple(sorted(word)) 
      try: 
       d[key].append(word) 
      except KeyError: 
       d[key] = [word] 
     return [w for ws in d.values() for w in ws if len(ws) > 1] 

Answer 2

Почему бы и нет?

str1 = "cafe" 
str2 = "face" 
def isanagram(s1,s2): 
    return all(sorted(list(str1)) == sorted(list(str2))) 

if isanagram(str1, str2): 
    print "Woo" 

Answer 3

Пропустить строки, которые вы уже разместили в комплекте. Не проверяйте их снова.

# @param strs: A list of strings 
# @return: A list of strings 
def anagrams(self, strs): 
    # write your code here 
    ret=set() 
    for i in range(0,len(strs)): 
     for j in range(i+1,len(strs)): 

      # If both anagrams exist in set, there is no need to compare them. 
      if i in ret and j in ret: 
       continue 

      if Solution.isanagram(strs[i],strs[j]): 
       ret.add(i) 
       ret.add(j) 

    return [strs[i] for i in list(ret)] 

Вы также можете выполнить сравнение длины в своем тесте анаграммы перед итерацией по буквам. Всякий раз, когда строки не имеют одинаковой длины, они не могут быть анаграммами. Кроме того, когда счетчик в chars достигает -1 при сравнении значений по t, просто верните false. Не перебирайте снова chars.

@staticmethod 
def isanagram(s, t): 
    # Test strings are the same length 
    if len(s) != len(t): 
     return False 

    chars={} 
    for i in s: 
     if i in chars: 
      chars[i]+=1 
     else: 
      chars[i]=1 

    for i in t: 
     if i not in chars: 
      return False 
     else: 
      chars[i]-=1 
      # If this is below 0, return false 
      if chars[i] < 0: 
       return False 

    for i in chars: 
     if chars[i]!=0: 
      return False 
    return True 

Answer 4

В дополнение к @ большой ответ Майка, вот хороший Pythonic способ сделать это:

import collections 


class Solution: 
    # @param strs: A list of strings 
    # @return: A list of strings 
    def anagrams(self, strs): 
     patterns = Solution.find_anagram_words(strs) 
     return [word for word in strs if ''.join(sorted(word)) in patterns] 

    @staticmethod 
    def find_anagram_words(strs): 
     anagrams = collections.Counter(''.join(sorted(word)) for word in strs) 
     return {word for word, times in anagrams.items() if times > 1} 

Answer 5

Вместо сравнения всех пар строк, вы можете просто создать словарь (или collections.defaultdict) сопоставление каждого из букв-слов с словами, имеющими эти значения. Для получения количества букв вы можете использовать collections.Counter. После этого вам просто нужно получить значения из этого dict. Если вы хотите, чтобы все слова были анаграммами любых других слов, просто объедините списки, содержащие более одной записи.

strings = ["cat", "act", "rat", "hut", "tar", "tact"] 
anagrams = defaultdict(list) 

for s in strings: 
    anagrams[frozenset(Counter(s).items())].append(s) 

print([v for v in anagrams.values()]) 
# [['hut'], ['rat', 'tar'], ['cat', 'act'], ['tact']] 
print([x for v in anagrams.values() if len(v) > 1 for x in v]) 
# ['cat', 'act', 'rat', 'tar'] 

Конечно, если вы предпочитаете не использовать встроенную функциональность вы можете с помощью всего нескольких строк так же, как хорошо использовать обычный dict вместо defaultdict и написать свой собственный Counter, подобное тому, что у вас есть в вашем isanagram метод, просто без части сравнения.