Поиск анаграммы Python (Оптимизация)

Question

Имеется задание, где нужно найти количество пар анаграмм.Я написал код, с использованием Counter'а, но он работает слишком медленно. Мне нужно , чтобы он до 10 секунд обрабатывал 100.000 слов.

Входные данные: n - количество слов (от 2 до 10^5) Каждая новая строка до 'n' слово из 10 латинских букв нижнего регистра.

Пример входа:

5
qwertyuiop
twoplussix
poiuytrewq
plustwosix
poiuqwerty

Пример вывода: 4

Мой код:

def comparing(tmp,stack):
    global counter
    ch = True
    if stack == -999:
        return counter
    for i in range(len(tmp)):
        if Counter(tmp[i]) == Counter(stack):
            counter+=1
            ch = False
    if ch == True:
        tmp.insert(-1,stack)

    counter = 0
n = int(input())
tmp = []
for i in range(n):
    tmp.append(input())


for i in range(n):
    x = tmp.pop(0)
    comparing(tmp,x)
print(comparing([0,0],-999))

Answer 1

Приведённый код многократно считает одно и то же - счётчики букв в слове.

Однако проще отсортировать буквы в каждом слове - получается ключ для поиска, и посчитать одинаковые ключи- да хоть тем же Counter

from collections import Counter

n = int(input())
cn = Counter()
for i in range(n):
    s = "".join(sorted(input()))
    cn[s] += 1
res = 0
for x in cn:
    t = cn[x]
    res += t*(t-1)//2
print(res)

Answer 2

from collections import Counter


def input_words():
    n = int(input())
    for _ in range(n):
        yield input()

def solve(word_iter):
    uniqueness = set()
    counter = Counter()
    for word in word_iter:
        if word not in uniqueness: # Не рассматриваем дубликаты
            uniqueness.add(word)
            key = ''.join(sorted(word))
            counter[key] += 1
    result = 0
    for key in counter:
        r = counter[key]
        # Кол-во сочетаний = r! / 2 (r-2)!
        result += r*(r-1)//2

    return result
# cnt = solve(input_words())
cnt = solve([
    'qwertyuiop',
    'twoplussix',
    'poiuytrewq',
    'plustwosix',
    'poiuqwerty',
    'poiuqwerty', # duplicate
])

print(cnt) # 4

Answer 3

Получилось решить задачу без дополнительных модулей, по примеру автора выше.

n = int(input())
d = {}

for i in range(n):
    s = "".join(sorted(input()))
    if s not in d:
        d[s] = 1
    else:
        d[s] += 1
res = 0
for i in d:
    res += d[i]*(d[i]-1)//2

print(res)

Answer 4

text=["car", "arc", "text", "etxt", "saf","fas"]
text_2=sorted(text)
k=0
n=[]
an = lambda x, y: sorted(x) == sorted(y)
for i in range( len(text_2)):
    if an(text[i], text_2[k])==True:
        k+=1
    
        n.append(an(text_2[i], text[k]))
    elif k==len(text_2):
            break
        
print(n.count(True))

БЛОГ НА HUSL

Поиск анаграммы Python (Оптимизация)

Ответы (4 шт):