Как найти повторы в строке python

Given a string, find all the duplicate characters which are similar to each other. Let us look at the example. 

Examples:

Input : hello
Output : l

Input : geeksforgeeeks
Output : e g k s

Naive approach:

The idea is to use a dictionary to keep track of the count of each character in the input string. The program iterates through the string and adds each character to the dictionary, incrementing the count if the character is already present in the dictionary. After iterating through the string, the program then iterates through the dictionary to find characters with a count greater than 1, indicating that they are duplicates. These duplicate characters are stored in a list and returned as the output.

Implementation:

['g', 'e', 'k', 's']

Time complexity: O(n), where n is the length of the input string. 
Auxiliary space: O(k), where k is the number of distinct characters in the input string.

We have discussed a solution in the below post. Print all the duplicates in the input string We can solve this problem quickly using the python Counter() method. 

The approach is very simple. 

1. Create a dictionary using the Counter method having strings as keys and their frequencies as values.
2. Declare a temp variable.
3. Print all the indexes from the keys which have values greater than 1. 

Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(n) // since we are creating a dictionary and at worst case all elements will be stored inside it.

Approach : Using count() method

Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(n) // since we are using an extra list and in the worst case all elements will be stored inside it.

Approach : Using filter() method

Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(n)// since we are using a set to store all the values and in the worst case all elements will be stored inside it.

Using sets: 

Algorithm:

• Create two empty sets, one to store unique characters and one to store duplicate characters.
• Iterate through each character in the string.
• If the current character is already in the unique_chars set, it is a duplicate, so add it to the duplicate_chars set. 
• Otherwise, add it to the unique_chars set.
• Return the duplicate_chars 
   

{'g', 's', 'e', 'k'}

Complexity Analysis:

The time complexity of this algorithm is O(n), where n is the length of the input string. 
The space complexity is also O(n), as the worst-case scenario is that all characters in the string are unique, and therefore all characters will be added to the char_set set.

Using functools.reduce method: 

Algorithm:

• Initialize test string. 
• Using reduce method on a string which iterates over each character of a string and performs a function on a string. 
•  The function checks whether the character index from the left of the string and the right of the string is the same or not and whether it is already in the result or not.   
• If any character satisfies the above condition then it is added to the result. 
• Print the result. 

Time Complexity: O(N)  where N is the length of the string
Auxiliary Space: O(M)  M is the length of the new string.t 

Last Updated :
05 May, 2023

Like Article

Save Article

Введение в тему

Regex, или регулярные выражения – язык для работы с текстом. Он позволяет производить поиск, замену и другие операции. Этот язык встроен во многие другие языки программирования и является де-факто стандартным инструментом для большинства проектов, связанных с обработкой больших текстов.

Введение в регулярные выражения

Как уже говорилось, регулярные выражения присутствуют во множестве языков программирования, и, уж точно, во всех языках общего назначения. Не стал исключением и Python, в котором они представлены модулем стандартной библиотеки re.

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

Для начала работы с регулярными выражениями, необходимо импортировать модуль re в Ваш модуль.

Что такое шаблон регулярного выражения и как его скомпилировать

Ядром Regex являются шаблоны – синтаксис, позволяющий описывать текст: какой он длины, из каких символов состоит, в каком регистре и так далее. На основе таких шаблоном производится поиск в тексте.

Простой пример. Шаблон, который описывает один любой символ: «.?». Здесь точка означает любой символ, а вопросительный знак говорит о количестве – строго одно повторение.

Вы можете передать шаблон регулярного выражения в переменную, если планируете использовать его несколько раз. Для этого используется метод compile.

import re

regex = re.compile('.?')

# Теперь этот шаблон можно использовать из переменной

print(regex.findall('qwerty'))
# Вывод:

['q', 'w', 'e', 'r', 't', 'y', '']

  

Как разделить текст

В модуле re существует два метода разбиения строки по шаблону:

re.split и метод split объекта regex (который мы получаем методом compile). Второй метод предпочтительнее если Вы собираетесь использовать один и тот же шаблон много раз. Разберём, как они работают на примере:

import re

regex = re.compile('.')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit. ' 
'Simple is better than complex. ' 
'Complex is better than complicated. ' 
'Flat is better than nested.'
print('regex.split:', regex.split(text))
print('re.split:', re.split('.', text))
# Вывод:

regex.split: ['Beautiful is better than ugly', ' Explicit is better than implicit', ' Simple is better than complex', ' Complex is better than complicated', ' Flat is better than nested', '']

re.split: ['Beautiful is better than ugly', ' Explicit is better than implicit', ' Simple is better than complex', ' Complex is better than complicated', ' Flat is better than nested', '']

  

Как видите, работают он одинаково. Здесь мы экранировали точку обратной косой чертой чтобы модуль re воспринял её именно как точку, а не как любой символ.

Поиск совпадений с использованием findall search и match

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

Что делает re findall

import re

regex = re.compile('is ......')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit. ' 
'Simple is better than complex. ' 
'Complex is better than complicated. ' 
'Flat is better than nested.'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['is better', 'is better', 'is better', 'is better', 'is better']

  

Метод findall ищет все участки текста, совпадающие с переданным шаблоном, и возвращает список, состоящий из найденных вхождений. В данном примере мы искали все участки, которые начинаются со слова ‘is’, пробела и шести любых символов после.

re search против re match

Метод match ищет по заданному шаблону в начале строки. Возвращает этот метод специальный объект, содержащий начальный и конечный индексы найденной подстроки:

import re

regex = re.compile('Beautiful')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit. ' 
'Simple is better than complex. ' 
'Complex is better than complicated. ' 
'Flat is better than nested.'
print('regex.match:', regex.match(text))
print('regex.match.start():', regex.match(text).start())
print('regex.match.end():', regex.match(text).end())
# Вывод:

regex.match: <re.Match object; span=(0, 9), match='Beautiful'>

regex.match.start(): 0

regex.match.end(): 9

  

Для того, чтобы вывести саму подстроку, придётся применить метод group:

import re

regex = re.compile('Beautiful')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit. ' 
'Simple is better than complex. ' 
'Complex is better than complicated. ' 
'Flat is better than nested.'
print('regex.match:', regex.match(text).group())
# Вывод:

regex.match: Beautiful

  

Метод search подобен функции match, но искать подстроки может в любом месте текста. Возвращает такой же объект, как и match.

import re

regex = re.compile('is .{6}')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit. ' 
'Simple is better than complex. ' 
'Complex is better than complicated. ' 
'Flat is better than nested.'
print('regex.search :', regex.search(text).group())
# Вывод:

regex.search : is better

  

Таким образом, отличие функций findall, search и match в способе поиска и возвращаемых значениях.

Как заменить один текст на другой используя регулярные выражения

Для замены одного фрагмента текста на другой используйте метод sub.
Тут, опять же существует два варианта:

import re

regex = re.compile('better')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit. ' 
'Simple is better than complex. ' 
'Complex is better than complicated. ' 
'Flat is better than nested.'# Первый вариант:
text = regex.sub('лучше', text)
print('regex.sub :', text)# Второй вариант:
text = re.sub('than', 'чем', text)
print('re.sub :', text)
# Вывод:

regex.sub : Beautiful is лучше than ugly. Explicit is лучше than implicit. Simple is лучше than complex. Complex is лучше than complicated. Flat is лучше than nested.

re.sub : Beautiful is лучше чем ugly. Explicit is лучше чем implicit. Simple is лучше чем complex. Complex is лучше чем complicated. Flat is лучше чем nested.

  

Группы регулярных выражений

Группы регулярных выражений — функция, позволяющая извлекать нужные объекты соответствия как отдельные элементы.

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

import re

# Без группировки:
regex = re.compile(r'w{4,9}sis')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit. ' 
'Simple is better than complex. ' 
'Complex is better than complicated. ' 
'Flat is better than nested.'
print('regex.findall_1:', regex.findall(text))
# С группировкой:
regex = re.compile(r'(w{4,9})sis')
print('regex.findall_2:', regex.findall(text))
# Вывод:

regex.findall_1: ['Beautiful is', 'Explicit is', 'Simple is', 'Complex is', 'Flat is']

regex.findall_2: ['Beautiful', 'Explicit', 'Simple', 'Complex', 'Flat']

  

Что такое жадное соответствие в регулярных выражениях

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

Проще всего это понять на примере:

import re

regex = re.compile(r'.*.')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit.'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['Beautiful is better than ugly. Explicit is better than implicit.']

  

Как вы можете видеть, Regex показала совпадение до последней точки, хотя точка встречалась и в конце первой строки. Это и есть жадный поиск. Для того, чтобы активировать ленивое поведение, надо добавить в конец шаблона вопросительный знак. При ленивом поиске re будет останавливаться на каждой встреченной точке:

import re

regex = re.compile(r'.*?.')
text = 'Beautiful is better than ugly. ' 
'Explicit is better than implicit.'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['Beautiful is better than ugly.', ' Explicit is better than implicit.']

  

Наиболее распространенный синтаксис и шаблоны регулярных выражений

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

• Специальные символы,
  • ‘.’ — любой символ;
  • ‘^’ — началу строки;
  • ‘$’ — конец строки;
  • ‘*’ — 0 или более повторений;
  • ‘+’ — 1 или более повторений;
  • ‘?’ — 0 или 1 повторений;
  • ‘*?’, ‘+?’,’??’ — ограничение жадности;
  • ‘{m}’ — m повторений;
  • ‘{m,n}’ — как можно больше повторений в промежутке от m до n ;
  • ‘{m,n}?’ — как можно меньше повторений в промежутке от m до n;
  • ‘’ — экранирование специальных символов;
  • ‘[]’ — символьный класс;
  • ‘|’ — или;
  • ‘(…)’ — группа с захватом;
• Расширения регулярных выражений,
  • ‘(?aiLmsux)’ — установка флагов регулярного выражения;
  • ‘(?aiLmsux-imsx:…)’ — установка и удаление флагов;
  • ‘(?:…)’ — группа без захвата;
  • ‘(?P<name>…)’ — именованная группа;
  • ‘(?P=name)’ — обратная ссылка на именованную группу;
  • ‘(?#…)’ — комментарий;
  • ‘(?=…)’ — опережающая позитивная проверка;
  • ‘(?!…)’ — опережающая негативная проверка;
  • ‘(?<=…)’ — позитивная ретроспективная проверка;
  • ‘(?<!…)’ — негативная ретроспективная проверка;
  • ‘(?(id/name)yes-pattern|no-pattern)’ — стараться соответствовать yes-pattern;
• Специальные последовательности.
  • ‘number’ — соответствие группы с тем же номером;
  • ‘A’ — только начало строки;
  • ‘b’ — пустая строка (начало или конц слова);
  • ‘B’ — пустая строка (НЕ начало или конец слова);
  • ‘d’ — любая десятичная цифра;
  • ‘D’ — НЕ десятичная цифра;
  • ‘s’ — пробельный символ;
  • ‘S’ — НЕ пробельный символ;
  • ‘w’ — символы, которые могут быть частью слова;
  • ‘W’ — символы, которые НЕ могут быть частью слова;
  • ‘Z’ — только конец строки;

Примеры регулярных выражений

Любой символ кроме новой строки

import re

regex = re.compile(r'.')
text = 'Beautiful is better than ugly.'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['B', 'e', 'a', 'u', 't', 'i', 'f', 'u', 'l', ' ', 'i', 's', ' ', 'b', 'e', 't', 't', 'e', 'r', ' ', 't', 'h', 'a', 'n', ' ', 'u', 'g', 'l', 'y', '.']

  

Всё, кроме точек и пробелов

import re

regex = re.compile(r'[^s,^.]')
text = 'Beautiful is better than ugly.'
print('regex.findall:', regex.findall(text))
# Вывод:
regex.findall: ['B', 'e', 'a', 'u', 't', 'i', 'f', 'u', 'l', 'i', 's', 'b', 'e', 't', 't', 'e', 'r', 't', 'h', 'a', 'n', 'u', 'g', 'l', 'y']

  

Любая цифра

import re

regex = re.compile(r'd+')
text = 'Date: 2021-08-11'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['2021', '08', '11']

  

Все, кроме цифры

import re

regex = re.compile(r'D+')
text = 'Date: 2021-08-11'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['Date: ', '-', '-']

  

Любая буква или цифра

import re

regex = re.compile(r'w+')
text = 'Date: 2021-08-11'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['Date', '2021', '08', '11']

  

Все, кроме букв и цифр

import re

regex = re.compile(r'W+')
text = 'Date: 2021-08-11'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: [': ', '-', '-']

  

Только буквы

import re

regex = re.compile(r'[A-Za-z]+')
text = 'Date: 2021-08-11'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['Date']

  

Соответствие заданное количество раз

import re

regex = re.compile(r'w{4}')
# Четыре буквы подряд
text = 'Beautiful is better than ugly.'
print('regex.findall_1:', regex.findall(text))
# От пяти до семи
regex = re.compile(r'w{5,7}')
print('regex.findall_2:', regex.findall(text))
# Вывод:

regex.findall_1: ['Beau', 'tifu', 'bett', 'than', 'ugly']

regex.findall_2: ['Beautif', 'better']

  

1 и более вхождений

import re

regex = re.compile(r'w+t+w+')
# Слова с одной или более буквами t подряд
text = 'Beautiful is better than ugly.'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['Beautiful', 'better']

  

Любое количество вхождений (0 или более раз)

import re

regex = re.compile(r'u+t*w+')
# Слова с одной или более буквами t подряд
text = 'Beautiful is better than ugly.'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['utiful', 'ugly']

  

0 или 1 вхождение

import re

regex = re.compile(r'u+t?w+')
# Слова с одной или более буквами t подряд
text = 'Beautiful is better than ugly.'
print('regex.findall:', regex.findall(text))
# Вывод:

regex.findall: ['utiful', 'ugly']

  

Граница слова

Для определения границ слова, то есть такого места в тексте, где рядом расположен символ, из которого может состоять слово (w) и пробел (s), используют символ b.

Пример:

import re

# Первые две буквы каждого слова
regex = re.compile(r'bww')
text = 'Beautiful is better than ugly.'
print('regex.findall_1:', regex.findall(text))
# Последние две буквы каждого слова
regex = re.compile(r'wwb')
print('regex.findall_2:', regex.findall(text))
# Вывод:

regex.findall_1: ['Be', 'is', 'be', 'th', 'ug']

regex.findall_2: ['ul', 'is', 'er', 'an', 'ly']