Какова сложность алгоритма?

Question

richvoronov @richvoronov

Какова сложность алгоритма?

Затрудняюсь с оценкой сложности алгоритма

var isValid = function(s) {
    let res = s;
    while (res.indexOf('()') !== -1 || res.indexOf('[]') !== -1 || res.indexOf('{}') !== -1) {
      res = res.replace('()', '');
      res = res.replace('[]', '');
      res = res.replace('{}', '');
    }

    return !res;
};

Вопрос задан более двух лет назад
255 просмотров

3 комментария

Подписаться 2 Средний 3 комментария

Олег Войтенко @OliverV

Вам по какой шкале?

У меня такая задачка была на собесе еще на джуна по JS. Это легкий алгоритм парсера строки с заменой подстрок.

Написано более двух лет назад
richvoronov @richvoronov Автор вопроса

спасибо,
ответил ниже другому автору вот так

глядя на `while(res.indexOf)` хочется сказать что O(n^2), но смущает меня `.replace`. Насколько я понимаю под капотом replace так же имеет цикл. Вот и хочу понять стоит ли его учитывать, либо я что-то не так понимаю

Написано более двух лет назад
res2001 @res2001

Операции indexOf можно вообще выкинуть, просто делайте replace в цикле. Причем сделайте 3 цикла (или вложенные циклы) и в каждом свой replace. Выполняйте replace в цикле до тех пор пока replace не вернет, что замен не было.
Не знаю как работает replace в JS, но можно replaceить не всю строку каждый раз, а с того места где закончился предыдущий replace. Или, если есть возможность делать replace всех вхождений, то надо его и использовать, тогда можно обойтись без циклов совсем.

Написано более двух лет назад

Вам по какой шкале?

У меня такая задачка была на собесе еще на джуна по JS. Это легкий алгоритм парсера строки с заменой подстрок.
спасибо,
ответил ниже другому автору вот так

глядя на `while(res.indexOf)` хочется сказать что O(n^2), но смущает меня `.replace`. Насколько я понимаю под капотом replace так же имеет цикл. Вот и хочу понять стоит ли его учитывать, либо я что-то не так понимаю
Операции indexOf можно вообще выкинуть, просто делайте replace в цикле. Причем сделайте 3 цикла (или вложенные циклы) и в каждом свой replace. Выполняйте replace в цикле до тех пор пока replace не вернет, что замен не было.
Не знаю как работает replace в JS, но можно replaceить не всю строку каждый раз, а с того места где закончился предыдущий replace. Или, если есть возможность делать replace всех вхождений, то надо его и использовать, тогда можно обойтись без циклов совсем.

Answer 1 · 2022-07-19 13:49:34

Slava Rozhnev @rozhnev

Fullstack programmer, DBA, медленно, дорого

O = 3n^2

Ответ написан более двух лет назад

Комментировать

Какова сложность алгоритма?

Войдите на сайт