IA
не массив а словарь только
Size: a a a
2020 May 13
КК
так это тоже n квадрат, к тому же менять итерируемый объект - очень плохая идея
IA
так это тоже n квадрат, к тому же менять итерируемый объект - очень плохая идея
я прошелся один раз по первому слову и один раз по второму слову
AA
я так тоже делал, почему плохая - там итерация каждая с начала идет
КК
я прошелся один раз по первому слову и один раз по второму слову
а. я подумал типа функцией replace. если так, то это линейное время
IA
def scramble(s1, s2):
sdict = {}
for i in s2:
sdict[i] = sdict.get(i, 0) + 1
for i in s1:
if len(sdict) > 0:
if i in sdict:
sdict[i] -= 1
if sdict[i] == 0:
del sdict[i]
else:
return True
return len(sdict) == 0
AA
чето нифига не оптимизируется ( Видимо там хак какой-то, типа побитового сдвига для умножения на 2
AA
с сортированными массивами попробовал тоже
КК
def scramble(s1, s2):
sdict = {}
for i in s2:
sdict[i] = sdict.get(i, 0) + 1
for i in s1:
if len(sdict) > 0:
if i in sdict:
sdict[i] -= 1
if sdict[i] == 0:
del sdict[i]
else:
return True
return len(sdict) == 0
это всё равно O от n квадрат
КК
потому что оператор in тоже имеет линейное время. значит у нас цикл в цикле
IA
потому что оператор in тоже имеет линейное время. значит у нас цикл в цикле
нет, в словаре доступ по ключу моментальный
IA
или я не совсем понял
КК
оператор in проверяет по значению, а не по ключу
КК
так что не моментальный
IA
словарь в питоне это хеш таблица, он не ищет по словарю, а вычисляет хеш и сразу же находит элемент
IA
ты сейчас говоришь про строчку if i in sdict: ?
IA
чето нифига не оптимизируется ( Видимо там хак какой-то, типа побитового сдвига для умножения на 2
ну у меня еще мысль может сет взять какойто хитрый
КК
а как мы узнаем достаточно ли вхождений того или иного символа?
IA
вот про это я и думаю сейчас, плюс я не знаю скорость создание сета, может за счет того что это встроенная питоновская функция то оно быстрее пойдет и тогда что-то с этим можно делать