Алгоритмы, связанные со строками
Поиск символа в строке
Реализую линейный поиск символа в строке.
Так как нужно найти один конкретный символ, а в строке - n символов, то проверить в худшем случае нужно будет все элементы. Значит, сложность будет равна O(n) - сколько элементов, столько и сравнений.
target = "a"
text = "mhtirogla"
success = False
for letter in text:
if letter == target:
success = True
break
if success:
print("Буква была найдена в строке")
else:
print("Буквы в строке нет")В строке было 9 букв, цикл сработал 9 раз, и мы нашли нужную букву. Всё сходится, и сложность O(n) подтвердилась, но что, если бы мы выполняли поиск в строке “algorithm”? Тогда бы мы нашли букву а на первой же итерации, цикл бы завершился и, получается, сложность была бы O(1)?
Нет. Big O говорит как раз о худшем случае для алгоритма. Когда пишем О(n), мы гарантируем, что, даже если всё будет плохо, мы найдём букву максимум за O(n).
Поиск подстроки в строке
Усложним предыдущую задачу: попробуем найти не один символ в строке, а маленькую строку внутри большой (подстроку в строке).
main_string = ‘Hello world!’ - основная строка.
sub_string = ‘ow’ - подстрока, которую алгоритм будет искать в основной строке.
Для решения «в лоб», с перебором всех вариантов, нужно пройти почти по всем символам строки и проверить, не начинается ли с текущего символа искомая нами подстрока. Мы берём символ, а затем начинаем цикл, сравнивая этот символ и следующие с подстрокой.
main_length = len(main_string)
sub_length = len(sub_string)
success = False
# Мы можем проходить не по всей строке.
# Например, если мы ищем подстроку из 6 букв в слове из 10 букв, то проверить нужно только первые 4 буквы, так как подстрока просто не поместится в остатке строки, если поиск будет начинаться с 5-й буквы.
# Пример:
# “1122334455” - весь текст;
# “123456” - подстрока, которую ищем.
# Надо проверить следующие варианты: начинаем с первого символа и проверяем шесть символов (столько, сколько их в подстроке)
# “112233” == “123456”?
# строки не равны, берём второй символ
# “122334” == “123456”?
# тоже нет
# “223344” == “123456”?
# “233445” == “123456”?
# “334455” == “123456”?
# А вот дальше двигаться нет смысла, так как в строке осталось всего 5 символов и они точно не могут быть равны подстроке из 6 символов:
# “34455” != “123456”
# Значит, наш цикл должен был пройти от 0 до 4 (10 − 6 = 4) включительно.
# Тогда, чтобы найти количество итераций в коде, нам нужно посчитать:(длина главной строки − длина подстроки + 1). +1 нужен, чтобы range дошёл до полученного числа включительно
count = main_length - sub_length + 1
for i in range(count):
j = 0
# j - счётчик для подсчёта совпадений
while j < sub_length and main_string[i + j] == sub_string[j]:
# Цикл продолжается, пока:
# 1) количество совпадений меньше длины подстроки (если они будут равны, то дальше проверку делать нет смысла);
# 2) взятые символы равны (с помощью j мы перебираем символы в строке, i используем как сдвиг, чтобы брать из главной строки срез, начиная с текущего символа).
j += 1
# Если после вложенного цикла число j равно длине подстроки, это значит, что мы нашли подстроку в нашей строке, цикл можно прерывать
if j == sub_length:
success = True
break
if success:
print('Подстрока найдена!')
else:
print('Такой подстроки в строке нет :(')Этот метод может быть неэффективным для длинных строк, так как его сложность составляет O(main_length * sub_length), где main_length - длина строки, а sub_length - длина подстроки. Однако это простой и понятный способ реализовать поиск подстроки в строке.
Проверка палиндрома
Палиндром - слово, фраза или последовательность символов, которые читаются одинаково ltr и rtl.
Например, слова «довод» и «комок» - палиндромы, потому что они читаются одинаково в обоих направлениях. Также палиндромами могут быть числа, такие как 121 или 12321.
Если есть строка text и нужно проверить, является ли она палиндромом, нужно убедиться, что символы её первой половины равны символам второй. Сделать это можно разными способами - рассмотрим несколько самых простых, которые можно реализовать без изучения дополнительных инструментов (кроме разве что индексов).
Вариант 1 (без использования индексов)
text = 'довод'
reversed_text = ''
for letter in text:
# Каждый символ строки добавляем В НАЧАЛО новой строки
reversed_text = letter + reversed_text
if text == reversed_text:
print('Это палиндром!')
else:
print('Не палиндром!')Так как для этого алгоритма нам надо пройти по каждому элементу строки, сложность такого алгоритма будет равна O(n).
Вариант 2 (с использованием индексов)
text = 'довод'
text_length = len(text)
success = True
# За одну итерацию мы будем проверять два символа (с начала и с конца), поэтому итераций можно сделать в два раза меньше (text_length // 2):
for i in range(text_length // 2):
# На каждой итерации сравниваем два символа:
# символ с начала text[i] с символом с конца text[-i - 1]
if text[i] != text[-i - 1]:
# Если хотя бы одна пара символов не совпадёт, то меняем флаг и завершаем цикл
success = False
break
if success:
print('Это палиндром!')
else:
print('Не палиндром!')Здесь мы перебираем не все элементы строки, а половину (длина строки // 2). Потому что за одну итерацию проверяем сразу 2 символа, один - с начала строки (индекс i), другой - с конца (-i - 1), а центральный символ нам вообще проверять нет необходимости.
Получается, что этот алгоритм эффективнее предыдущего - его сложность примерно равна O(n/2). Она не дотягивает до O(log n), но это всё же лучше, чем O(n).