1

Формат ввода:

В первой строке идёт целое число n (1 ≤ n ≤ 100 000), количество исходных слов.

Далее следует n слов, по одному слову в строке, слова могут идти в разном регистре!

Формат вывода:

В одной строке должны идти слова, которые являются анаграммами друг для друга, в нижнем регистре, через пробел. Порядок слов — лексикографический (как в словаре). Порядок строк так же лексикографический.

Не прошу решить задачу, прошу прояснить один момент мне. Мой код:

n = int(input())
s = []
for i in range(n):
    s.append(input().lower())
s = sorted(s)
print(s)
for i in s:
    anagrams = []
    for j in s:
        if sorted(list(i)) == sorted(list(j)):
            anagrams.append(j)
    if len(anagrams) > 1:
        print(*anagrams)
        for j in anagrams:
            del s[s.index(j)]

Я собираю слова в один список. После прохожусь по нему: беру первое слово и после ещё раз прохожусь по списку слов для того чтобы найти анаграммы, найдя все я помещаю их в список anagrams. Для того чтобы слова не повторялись, я прохожусь по списку анаграмм, и удалю из списка s все слова которые встречаются в списке anagram. Возникает проблема, мне нужно чтобы цикл проходился по уже изменённому списку, например был такой список:

['окорок', 'петлей', 'плетей', 'рококо', 'теплей', 'тишь', 'томно', 'тонко', 'тонок', 'тоном', 'шить']

И при удалении анаграмм, окорок и рококо, список стал иметь вид:

['петлей', 'плетей', 'теплей', 'тишь', 'томно', 'тонко', 'тонок', 'тоном', 'шить']

И цикл уже начинался со слова 'петлей', но такого не происходит, прошу описать решение этой проблемы, и почему она возникает.

1 ответ 1

1

Нельзя менять список по которому вы итерируетесь. Есть три способа обойти это ограничение:

  1. Итерируйтесь не по списку, а по его индексам
    i = 0
    while i < len(s):
        # можно удалять, вставлять, делать со списком что угодно
        i += 1
  1. Итерируйтесь по списку, но результат записывайте в новый список. В вашем конкретном случае этот рецепт не применим - два цикла, в старых и новых списках запутаетесь.

  2. Поменяйте алгоритм. Ваш алгоритм работает за квадрат, задачу можно решить за линейное время, если изменить структуры данных. Подсказка: соберите анаграммы в словарь: {ключ: [слова соответствующие ключу], ...}.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.