J
Кто хорошо знает работу регулярок — какова сложность алгоритма?
Size: a a a
2021 January 14
J
Оптимальный O(n)
J
А как работает регулярка?
J
Под капотом
П
напрямую зависит от конкретной регулярки, можно ведь в лоб искать, а можно рекурсии понакрутить
J
Какова скорость поиска “([a-z]).*\1”? Больше чем O(n)?
DE
Так их не мерят
J
Я к чему, есть задание написать алгоритм который определит isogram или нет со сложностью O(n)
П
ну хочет он мерять, почему бы и нет
П
Какова скорость поиска “([a-z]).*\1”? Больше чем O(n)?
равно O(n)
J
Павел
равно O(n)
Вот как бы так должно быть. По логике.
J
Но может быть и O(n^2)
СД
^(?:([a-z])(?!.*\1))*$
ну вот это судя по дебагу n2
П
Но может быть и O(n^2)
от чего зависит слово "может" ?
J
Если движок берёт первый символ и затем смотрит всю строку есть ли совпадение, затем второй, третий... то это brute force == O(n^2)
J
У меня есть подозрение, что именно так и работает движок регулярки
J
Берёт последовательно один символ за другим и просматривает строку до конца
П
это уже зависит от кривизны используемого движка регекспа, нужно брать только один. Или как раз нужно сравнивать именно движки?
J
Java
DE
function isIsogram (str) {
const cut = str.replace('-', '')
return new Set(cut).size === cut.length
}