Как оптимизировать код [python]?

Question

Как оптимизировать код [python]?

Рейтинг: -1Ответов: 1Опубликовано: 28.01.2023

Решаю задание: "Даны две строки X и Y. Напишите программу, которая посчитает, сколько подстрок строки Y являются анаграммами строки X". У меня есть код, он работает, но на 10 тесте он выдаёт ошибку, потому что тратится слишком много времени. Подскажите, пожалуйста, как можно оптимизировать код.

x = str(input())
y = str(input())

len_x = len(x)

list_x = list(x)
list_x.sort()

count = 0
for i in range(len(y)):
    slice_y = list(y[i:i + len_x])
    slice_y.sort()
    if slice_y == list_x:
        count += 1
print(count)

python строки алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 1

Создаёте словарик, содержащий символы X и их счётчики (dct = {'a':2; 'l':1; 'v':1} для 'lava')

Заводите переменную nonmatch_cnt = len(dct)

Для первых len(x) символов из Y делаете вот что - если символ есть в словаре, отнимаете от счётчика 1. Если данный счётчик становится равным нулю - отнимаете единицу от nonmatch_cnt, а если из нуля становится ненулевым - добавляете единицу к nonmatch_cnt

Проходите в цикле окном длиной len(x) по длине строки Y, на каждом шаге обрабатывая уходящий из окна символ (первый) и входящий (новый), как описано выше (для уходящего символа, имеющегося в словаре, к соотв. счетчику единицу прибавляем)

В моменты, когда nonmatch_cnt равен нулю - в окне находится анаграмма строки X (при этом количество каждого символа в окне равно количеству появлений соотв. символа в X)

Время работы линейное O(len(Y))

x:lava   y:aavalal
4 шага
dct                          nonmatch_cnt    
{'a':-1; 'l':1; 'v':0}        2
{'a':0; 'l':0; 'v':0}         0   *
{'a':0; 'l':0; 'v':0}         0   *
{'a':0; 'l':-1; 'v':1}        2

Как оптимизировать код [python]?

Ответы