Как найти повторяющиеся символы в строке python

Никто не использует re ! Время для ответа [ab] с помощью встроенного модуля регулярных выражений;)

Нахождение всех максимальных подстрок, которые повторяются

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

Поиск всех повторяющихся подстрок, включая перекрытия

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

Если вы хотите в дополнение к самым длинным повторяющимся строкам все подстроки, то:

Это гарантирует, что для длинных подстрок, которые имеют повторение, у вас также есть меньшая подстрока — например. «sample» и «достаточно», найденные кодом re.search ; но также «samp», «sampl», «amp» добавлены вышеупомянутым фрагментом.

Подсчет матчей

Поскольку (по замыслу) подсчитываемые нами подстроки не перекрываются, метод count является подходящим способом:

Полученные результаты

Нахождение максимальных подстрок:

С оригиналом вопроса mystring :

С образцом mystring_overlap :

Нахождение всех подстрок:

С оригиналом вопроса mystring :

. и если мы добавим код для получения всех подстрок , то, конечно, мы получим абсолютно все подстроки:

С образцом mystring_overlap :

Будущая работа

Можно отфильтровать результаты поиска всех подстрок , выполнив следующие действия:

• принять матч «А»
• проверьте, является ли это совпадение подстрокой другого совпадения, назовите его «B»
• если есть совпадение «B», проверьте счетчик в этом совпадении «B_n»
• если «A_n = B_n», то удалить A
• перейти к первому шагу

Не может быть так, что «A_n B_n», это означает, что имеется некоторое дополнительное совпадение с меньшей подстрокой, поэтому это отдельная подстрока, потому что она повторяется в месте, где B не повторяется.

Подсчет повторяющихся символов в строке в Python

Я хочу подсчитать количество раз, когда каждый символ повторяется в строке. Есть ли какой-либо конкретный способ сделать это, кроме сравнения каждого символа строки из A-Z и увеличить счетчик?

обновление (в отношении Антония): все, что вы предлагали до сих пор я должен написать 26 раз. Есть ли более простой способ?

15 ответов

моей первой идеей было сделать это:

это не очень хорошая идея, однако! Это будет сканировать строку 26 раз, поэтому вы потенциально сделаете в 26 раз больше работы, чем некоторые другие ответы. Вы действительно должны сделать это:

это гарантирует, что вы пройдете через строку только один раз, а не 26 раз.

кроме того, ответ Алекса отличный — я не был знаком с модулем коллекций. Я буду использовать это в будущее. Его ответ более лаконичен, чем мой, и технически превосходит мой. Я рекомендую использовать его код поверх моего.

A collections.defaultdict как dict (подклассы, на самом деле), но когда запись ищется и не найдена, вместо того, чтобы сообщать, что у нее ее нет, она делает ее и вставляет ее, вызывая предоставленный 0-аргумент вызываемым. Наиболее популярными являются defaultdict(int) , для подсчета (или, что эквивалентно, для создания структуры данных multiset AKA bag) и defaultdict(list) , что навсегда избавляет от необходимости использовать .setdefault(akey, []).append(avalue) и подобные неуклюжие идиомы.

Итак, как только вы это сделаете d — это дикт-как контейнер сопоставляет каждый символ с количеством раз, когда он появляется, и вы можете излучать его любым способом, конечно. Например, самый популярный персонаж сначала:

в Python 2.7+ включает в себя сборники.Счетчик класс:

Это самый короткий, самый практичный, который я могу придумать, не импортируя дополнительные модули.

print d [‘a’] выведет 2

и это тоже быстро.

Сравнение Производительности

так как мне «нечего было делать» (поймите: у меня было просто много работы), я решил сделать маленький конкурс производительность. Я собрал самые разумные или интересные ответы и сделал некоторые простые timeit на CPython 3.5.1 на них. Я проверял их только с одной строкой, которая типичный вход в моем случае:

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

не изобретайте колесо

Python сделал это простым для нас. The collections.Counter класс делает именно то, что мы хотим и многое другое. Его использование является самым простым из всех упомянутых здесь методов.

принято от @адррес oefe, нашел

Counter идет дополнительная миля, которая почему так долго.

Dictionary словарь, comprende?

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

я сам это придумал.

это пройдет s от начала до конца, и для каждого символа он будет считать число о его появлениях в s . С s содержит повторяющиеся символы, описанный выше метод поиски s несколько раз для одного и того же персонажа. Результат, естественно, всегда один и тот же. Так давай посчитаем. количество вхождений только один раз для каждого персонажа.

я сам придумал это, и так и сделал @IrshadBhat

лучше. Но мы все еще должны искать через строку, чтобы подсчитать вхождения. Один поиск каждого особый характер. Это означает, что мы будем читать строку более однажды. Мы можем сделать даже лучше! Но для этого мы должны сойти с декларативистской высоты и спуститься в императивное мышление.

красивый код

АКА должен поймать их всех!

вдохновленный @anthony

Ну, попробовать стоило. Если вы копаетесь в источнике Python (я не могу сказать с уверенностью, потому что Я никогда этого не делал), вы, вероятно, найдете это когда вы делаете except ExceptionType , Python должен проверить, действительно ли вызванное исключение имеет значение ExceptionType или какой-то другой тип. Просто на всякий случай, давайте посмотрим, сколько времени это займет, если мы опустим этот чек и поймаем все исключения.

сделал @anthony

это экономит некоторое время, поэтому может возникнуть соблазн использовать это как своего рода оптимизацию.
не делай этого! или на самом деле делать. Сделать его теперь:

вы видите? Он ловит KeyboardInterrupt , помимо прочего. На самом деле, он ловит все есть исключения. Включая те, о которых вы, возможно, даже не слышали, как SystemExit .

теперь вернемся к подсчету букв и цифр и других символов.

играть догонялки

исключения-это не путь. Вы должны стараться изо всех сил, чтобы догнать их, и когда Вы, наконец, они просто блюют на тебя, а потом поднимают брови, как будто это твоя вина. К счастью, храбрый ребята проложили нам путь, чтобы мы могли избавиться от исключений, по крайней мере, в этом небольшом упражнении.

на dict класс имеет хороший метод — get — что позволяет нам получить элемент из словарь, прямо как d[k] . Кроме тех случаев, когда ключ k is не в словаре, он может вернуться значение по умолчанию. Давайте использовать этот метод вместо того, чтобы возиться с исключениями.

заслуга @Usman

почти так же быстро, как на основе понимания дикт. На больших входах это, вероятно, будет еще быстрее.

Используйте правильный инструмент для работы

по крайней мере, слабо знающий программист Python, первое, что приходит на ум возможно defaultdict . Он делает почти то же самое, что и версия выше, за исключением значение, вы даете ему значение завод. Это может вызвать некоторые накладные расходы, потому что значение имеет быть «построенным» для каждого отсутствующего ключа индивидуально. Давайте посмотрим, как это работает.

Надежда @AlexMartelli не распнет меня за from collections import defaultdict

не так уж плохо. Я бы сказал, что увеличение времени исполнения-это небольшой налог для оплаты улучшенный удобочитаемость. Тем не менее, мы также выступаем за производительность, и мы не будем останавливаться на достигнутом. Давай продолжим. и заполнить словарь нулями. Тогда нам не придется проверять каждый раз, если элемент уже есть.

снимаю шляпу перед @sqram

это хорошо. В три раза быстрее, чем Counter , но все же достаточно просто. Лично это мой любимый, если вы не хотите добавлять новых персонажей позже. И даже если вы можете продолжай. Это просто менее удобно, чем было бы в других версиях:

практичность бьет чистоты (за исключением случаев, когда это не очень практично)

теперь немного другой вид борьбы. @IdanK придумал кое-что интересное. Вместо использования хэш-таблицы (a.к. a. словарь a.к. a. dict ), мы можем избежать риска хеширования и последующие затраты на их разрешение. Мы также можем избежать хэширования ключа, и лишнее свободное место за столом. Мы можем использовать list . Значения ASCII символов будут индексы и их подсчеты будут значениями. Как отметил @IdanK, этот список дает нам константу время доступа к счету персонажа. Все, что нам нужно сделать, это преобразовать каждый символ из str в int использование встроенной функции ord . Это даст нам индекс в список, который мы будем затем используйте для увеличения количества характер. Итак, мы делаем следующее: мы инициализируем список с нулями выполните задание, а затем преобразуйте список в dict . Это dict будет содержать только те символы, которые имеют ненулевые счетчики, чтобы сделать его совместимым с другими версиями.

в качестве примечания этот метод используется в алгоритме линейной сортировки, известном как графа вроде или подсчет вроде. Это очень эффективно, но диапазон сортируемых значений есть ограничено, так как каждое значение должно иметь свой собственный счетчик. Сортировка последовательности 32-разрядных целых чисел, Потребуется 4,3 миллиарда счетчиков.

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

все равно плохо. Но подождите, что такое [0 for _ in range(256)] ? Разве мы не можем написать это проще? Как насчёт [0] * 256 ? Так чище. Но будет ли он работать лучше?

значительно. Теперь давайте положим словарь обратно в.

почти в шесть раз медленнее. Почему так долго? Потому что, когда мы enumerate(counts) мы чтобы проверить каждый из 256 подсчетов и посмотреть, равен ли он нулю. Но мы уже знаем, какие из них ноль, а какие нет.

вероятно, это не будет намного лучше, чем это, по крайней мере, не для такого небольшого ввода. Плюс это только используется для 8-битных символов EASCII. О блять!

и победитель.

да. Даже если вам нужно каждый раз проверять, есть ли c находится в d для этого входа это самый быстрый путь. Нет предварительной популяции d сделает это быстрее (опять же, для этот вход). Это намного больше многословнее, чем Counter или defaultdict , но и более эффективным.

это все люди

это небольшое упражнение преподает нам урок: при оптимизации всегда измеряйте производительность, в идеале предполагаемое входов. Оптимизируйте для общего случая. Не предположим, что-то на самом деле более эффективно только потому, что его асимптотическая сложность ниже. И последнее, но не менее важное: читаемость в виду. Попробуйте найти компромисс между» дружественным к компьютеру «и»дружественным к человеку».

обновление

мне сообщили @MartijnPieters функции collections._count_elements доступен в Python 3.

эта функция реализована в C, так это должно быть быстрее, но это дополнительное производительности по цене. Цена несовместимости С Python 2 и, возможно, даже будущих версий, так как мы используем частную функцию.

[. ] имя с префиксом подчеркивания (например, _spam ) следует рассматривать как непубличную часть API (будь то функция, метод или элемент данных). Его следует рассматривать в качестве детали осуществления и могут быть изменены без предварительного уведомления.

41 вопрос о работе со строками в Python

Я начал вести список наиболее часто используемых функций, решая алгоритмические задачи на LeetCode и HackerRank.

Быть хорошим программистом — это не значит помнить все встроенные функции некоего языка. Но это не означает и того, что их запоминание — бесполезное дело. Особенно — если речь идёт о подготовке к собеседованию.

Хочу сегодня поделиться со всеми желающими моей шпаргалкой по работе со строками в Python. Я оформил её в виде списка вопросов, который использую для самопроверки. Хотя эти вопросы и не тянут на полноценные задачи, которые предлагаются на собеседованиях, их освоение поможет вам в решении реальных задач по программированию.

1. Как проверить два объекта на идентичность?

Оператор is возвращает True в том случае, если в две переменные записана ссылка на одну и ту же область памяти. Именно об этом идёт речь при разговоре об «идентичности объектов».

Не стоит путать is и == . Оператор == проверяет лишь равенство объектов.

Обратите внимание на то, что animals и even_more_animals не идентичны, хотя и равны друг другу.

Кроме того, существует функция id() , которая возвращает идентификатор адреса памяти, связанного с именем переменной. При вызове этой функции для двух идентичных объектов будет выдан один и тот же идентификатор.

2. Как проверить то, что каждое слово в строке начинается с заглавной буквы?

Существует строковый метод istitle() , который проверяет, начинается ли каждое слово в строке с заглавной буквы.

3. Как проверить строку на вхождение в неё другой строки?

Существует оператор in , который вернёт True в том случае, если строка содержит искомую подстроку.

4. Как найти индекс первого вхождения подстроки в строку?

Есть два метода, возвращающих индекс первого вхождения подстроки в строку. Это — find() и index() . У каждого из них есть определённые особенности.

Метод find() возвращает -1 в том случае, если искомая подстрока в строке не найдена.

Метод index() в подобной ситуации выбрасывает ошибку ValueError .

5. Как подсчитать количество символов в строке?

Функция len() возвращает длину строки.

6. Как подсчитать то, сколько раз определённый символ встречается в строке?

Ответить на этот вопрос нам поможет метод count() , который возвращает количество вхождений в строку заданного символа.

7. Как сделать первый символ строки заглавной буквой?

Для того чтобы это сделать, можно воспользоваться методом capitalize() .

8. Что такое f-строки и как ими пользоваться?

В Python 3.6 появилась новая возможность — так называемые «f-строки». Их применение чрезвычайно упрощает интерполяцию строк. Использование f-строк напоминает применение метода format() .

При объявлении f-строк перед открывающей кавычкой пишется буква f .

9. Как найти подстроку в заданной части строки?

Метод index() можно вызывать, передавая ему необязательные аргументы, представляющие индекс начального и конечного фрагмента строки, в пределах которых и нужно осуществлять поиск подстроки.

Обратите внимание на то, что вышеприведённая конструкция возвращает 23 , а не 0 , как было бы, не ограничь мы поиск.

10. Как вставить содержимое переменной в строку, воспользовавшись методом format()?

Метод format() позволяет добиваться результатов, сходных с теми, которые можно получить, применяя f-строки. Правда, я полагаю, что использовать format() не так удобно, так как все переменные приходится указывать в качестве аргументов format() .

11. Как узнать о том, что в строке содержатся только цифры?

Существует метод isnumeric() , который возвращает True в том случае, если все символы, входящие в строку, являются цифрами.

Используя этот метод, учитывайте то, что знаки препинания он цифрами не считает.

12. Как разделить строку по заданному символу?

Здесь нам поможет метод split() , который разбивает строку по заданному символу или по нескольким символам.

13. Как проверить строку на то, что она составлена только из строчных букв?

Метод islower() возвращает True только в том случае, если строка составлена исключительно из строчных букв.

14. Как проверить то, что строка начинается со строчной буквы?

Сделать это можно, вызвав вышеописанный метод islower() для первого символа строки.

15. Можно ли в Python прибавить целое число к строке?

В некоторых языках это возможно, но Python при попытке выполнения подобной операции будет выдана ошибка TypeError .

16. Как «перевернуть» строку?

Для того чтобы «перевернуть» строку, её можно разбить, представив в виде списка символов, «перевернуть» список, и, объединив его элементы, сформировать новую строку.

17. Как объединить список строк в одну строку, элементы которой разделены дефисами?

Метод join() умеет объединять элементы списков в строки, разделяя отдельные строки с использованием заданного символа.

18. Как узнать о том, что все символы строки входят в ASCII?

Метод isascii() возвращает True в том случае, если все символы, имеющиеся в строке, входят в ASCII.

19. Как привести всю строку к верхнему или нижнему регистру?

Для решения этих задач можно воспользоваться методами upper() и lower() , которые, соответственно, приводят все символы строк к верхнему и нижнему регистрам.

20. Как преобразовать первый и последний символы строки к верхнему регистру?

Тут, как и в одном из предыдущих примеров, мы будем обращаться к символам строки по индексам. Строки в Python иммутабельны, поэтому мы будем заниматься сборкой новой строки на основе существующей.

21. Как проверить строку на то, что она составлена только из прописных букв?

Имеется метод isupper() , который похож на уже рассмотренный islower() . Но isupper() возвращает True только в том случае, если вся строка состоит из прописных букв.

22. В какой ситуации вы воспользовались бы методом splitlines()?

Метод splitlines() разделяет строки по символам разрыва строки.

23. Как получить срез строки?

Для получения среза строки используется синтаксическая конструкция следующего вида:

Здесь step — это шаг, с которым будут возвращаться символы строки из диапазона start_index:end_index . Значение step , равное 3, указывает на то, что возвращён будет каждый третий символ.

24. Как преобразовать целое число в строку?

Для преобразования числа в строку можно воспользоваться конструктором str() .

25. Как узнать о том, что строка содержит только алфавитные символы?

Метод isalpha() возвращает True в том случае, если все символы в строке являются буквами.

26. Как в заданной строке заменить на что-либо все вхождения некоей подстроки?

Если обойтись без экспорта модуля, позволяющего работать с регулярными выражениями, то для решения этой задачи можно воспользоваться методом replace() .

27. Как вернуть символ строки с минимальным ASCII-кодом?

Если взглянуть на ASCII-коды элементов, то окажется, например, что прописные буквы имеют меньшие коды, чем строчные. Функция min() возвращает символ строки, имеющий наименьший код.

28. Как проверить строку на то, что в ней содержатся только алфавитно-цифровые символы?

В состав алфавитно-цифровых символов входят буквы и цифры. Для ответа на этот вопрос можно воспользоваться методом isalnum() .

29. Как удалить пробелы из начала строки (из её левой части), из её конца (из правой части), или с обеих сторон строки?

Здесь нам пригодятся, соответственно, методы lstrip() , rstrip() и strip() .

30. Как проверить то, что строка начинается с заданной последовательности символов, или заканчивается заданной последовательностью символов?

Для ответа на этот вопрос можно прибегнуть, соответственно, к методам startswith() и endswith() .

31. Как закодировать строку в ASCII?

Метод encode() позволяет кодировать строки с использованием заданной кодировки. По умолчанию используется кодировка utf-8 . Если некий символ не может быть представлен с использованием заданной кодировки, будет выдана ошибка UnicodeEncodeError .

32. Как узнать о том, что строка включает в себя только пробелы?

Есть метод isspace() , который возвращает True только в том случае, если строка состоит исключительно из пробелов.

33. Что случится, если умножить некую строку на 3?

Будет создана новая строка, представляющая собой исходную строку, повторённую три раза.

34. Как привести к верхнему регистру первый символ каждого слова в строке?

Существует метод title() , приводящий к верхнему регистру первую букву каждого слова в строке.

35. Как объединить две строки?

Для объединения строк можно воспользоваться оператором + .

36. Как пользоваться методом partition()?

Метод partition() разбивает строку по заданной подстроке. После этого результат возвращается в виде кортежа. При этом подстрока, по которой осуществлялась разбивка, тоже входит в кортеж.

37. Строки в Python иммутабельны. Что это значит?

То, что строки иммутабельны, говорит о том, что после того, как создан объект строки, он не может быть изменён. При «модификации» строк исходные строки не меняются. Вместо этого в памяти создаются совершенно новые объекты. Доказать это можно, воспользовавшись функцией id() .

При конкатенации ‘Rise each day before the sun’ и ‘ if its a weekday’ в памяти создаётся новый объект, имеющий новый идентификатор. Если бы исходный объект менялся бы, тогда у объектов был бы один и тот же идентификатор.

38. Если объявить одну и ту же строку дважды (записав её в 2 разные переменные) — сколько объектов будет создано в памяти? 1 или 2?

В качестве примера подобной работы со строками можно привести такой фрагмент кода:

При таком подходе в памяти создаётся лишь один объект. Когда я столкнулся с этим в первый раз, мне это не показалось интуитивно понятным. Но этот механизм помогает Python экономить память при работе с длинными строками.

Доказать это можно, прибегнув к функции id() .

39. Как пользоваться методами maketrans() и translate()?

Метод maketrans() позволяет описать отображение одних символов на другие, возвращая таблицу преобразования.

Метод translate() позволяет применить заданную таблицу для преобразования строки.

Обратите внимание на то, что в строке произведена замена символов a , b , c и s , соответственно, на символы 1 , 2 , 3 и S .

40. Как убрать из строки гласные буквы?

Один из ответов на этот вопрос заключается в том, что символы строки перебирают, пользуясь механизмом List Comprehension. Символы проверяют, сравнивая с кортежем, содержащим гласные буквы. Если символ не входит в кортеж — он присоединяется к новой строке.

41. В каких ситуациях пользуются методом rfind()?

Метод rfind() похож на метод find() , но он, в отличие от find() , просматривает строку не слева направо, а справа налево, возвращая индекс первого найденного вхождения искомой подстроки.

Итоги

Я часто объясняю одному продакт-менеджеру, человеку в возрасте, что разработчики — это не словари, хранящие описания методов объектов. Но чем больше методов помнит разработчик — тем меньше ему придётся гуглить, и тем быстрее и приятнее ему будет работаться. Надеюсь, теперь вы без труда ответите на рассмотренные здесь вопросы.

Уважаемые читатели! Что, касающееся обработки строк в Python, вы посоветовали бы изучить тем, кто готовится к собеседованию?