Содержание

Определяем, все ли символы в строке уникальны. Разбор задачи

Давайте решим простую задачку, связанную с обработкой строк в Python.

Первый подход: брутфорс

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

Начнем с определения метода (можете работать в Repl.it, а можете воспользоваться просто карандашом и бумагой). Наш метод будет принимать одну строку в качестве параметра. Ее мы обозначим как s .

Дальше мы определим наш первый цикл for . Вообще у нас будут вложенные циклы, а этот будет перебирать все символы в строке до предпоследнего (включительно). Почему не до последнего? Потому что каждый из этих символов мы будем сравнивать с теми, которые идут после него, а за последним больше нет других символов.

Теперь давайте сделаем второй цикл for внутри первого. Он будет начинаться от следующей позиции в списке, которой мы назначим индекс j . Индекс j будет расти до конца списка, а элементы под этим индексом будут сравниваться с символом под индексом i . В случае совпадения мы вернем False — это будет означать, что не все символы в строке уникальны.

Наконец, нам нужно где-нибудь вернуть True. Если вложенный цикл for успешно сравнил все символы и не нашел совпадений, значит, все символы в строке уникальны. Поэтому мы возвращаем True за пределами вложенного цикла.

Вот и все! Вызов is_unique(«Hello») должен вернуть False, а is_unique(«Bye») — True.

Временная и пространственная сложность брутфорс-метода

Прежде всего, наше решение удовлетворяет требованию «никаких дополнительных структур данных». Мы просто перебираем в цикле строку, не сохраняя информацию в новой структуре. Это дает нам пространственную сложность O(1), которая не зависит от длины строки.

Более оптимальный подход: сортировка строки

Теперь, когда мы рассмотрели брутфорс, давайте перейдем к более элегантным решениям. Давайте посмотрим, нельзя ли применить здесь концепцию поиска и сортировки. Если мы отсортируем строку, мы сможем перебирать ее в цикле, проверяя, не совпадает ли каждый из символов с предыдущим.

Метод Python .sort() работает только со списками. Так что наша первая задача — превратить строку в список символов. Мы показываем, как это делается, что если вы дойдете до собеседования с решением задач у доски, такие вещи у вас должны уже от зубов отскакивать.

Цикл for перебирает все символы в строке s и возвращает каждый символ. Мы записываем результат в список, взяв цикл в квадратные скобки.

Превратив строку в список, мы можем вызвать метод sort() .

Теперь мы можем перебрать список. Мы будем сравнивать каждую букву с предыдущей. Сделать это можно двумя способами. Можно проитерировать каждый индекс, с первого (если таковой существует) до последнего. А если не отслеживать индекс, можно сохранять предыдущую букву в переменную. Инициализировать переменную можно как пустую строку.

Можно превратить это в предложение if . Давайте используем в качестве имени переменной letter , а не char , чтобы не путать с тем, что мы делали ранее, когда превращали строку в список.

Наконец, если цикл for успешно отработает и не найдет совпадений, мы вернем True за пределами цикла. Все вместе это выглядит так:

Временная сложность решения с использованием метода sort()

Временная сложность этого решения зависит от временной сложности самого метода sort(). Python использует Timsort — гибрид сортировки слиянием и вставками (если вам это о чем-то говорит). Его временная сложность в среднем и наихудшем случае — O(N log N). Кроме того, мы перебираем список в цикле N раз, но этим можно пренебречь, потому что O(N log N) больше.

Однако, поскольку мы создали новый список для сортировки строки, мы не выполнили требование насчет отсутствия дополнительных структур данных.

Решение, еще более оптимальное с точки зрения временной сложности: использование словаря

В Python есть библиотека с дефолтным словарем — defaultdict. Она позволяет нам задавать значения по умолчанию: при вызове ключа, которого нет в словаре, будет создана пара из этого ключа и дефолтного значения. Это избавляет нас от необходимости проверять, есть ли ключ в списке, перед поиском его значения.

Мы можем назначить нашему словарю dd тип bool , таким образом дефолтное значение всегда будет False.

Теперь давайте напишем цикл for . Мы переберем в цикле все символы в строке, проверяя их значение. Если значение будет True, это будет означать, что такой символ нам уже попадался. В таком случае мы вернем False. Если значение будет False (а defaultdict «выдаст» его любому ключу, которого еще нет в словаре), мы присвоим этому символу значение True.

Наконец, мы вернем True за пределами цикла, если каждый символ встретится только один раз.

Временная сложность решения со словарем

Мы перебираем список N раз, кроме того доступ к каждому элементу словаря имеет временную сложность O(1). Таким образом временная сложность этого решения — O(N), а это даже лучше, чем в предыдущем способе. Работая над программами, вы увидите, что компромиссы с пространственной и временной сложностью — ваши постоянные спутники, а то, какое решение считать наилучшим, зависит от ситуации.

Английский для программистов

Наш телеграм канал с тестами по английскому языку для программистов. Английский это часть карьеры программиста. Поэтому полезно заняться им уже сейчас

[expert_bq id=»1570″]Часто такая проблема возникает с юридическими текстами, в которых требуется дословное цитирование названий, а иногда и текста законов и постановлений. Если же вы хотите что-то уточнить, обращайтесь ко мне![/expert_bq] Так как с технической точки зрения невозможно просканировать весь массив данных в интернете, алгоритм проверки выбирает определенное количество случайных сайтов, с которым обнаружено совпадение. Перечень каждый раз меняется, поэтому в проверку попадают новые сайты, соответственно процент совпадений может отличаться.