Кодирование строк, разворот и палиндромы
Реализуйте разворот слов на месте, кодирование длин серий и проверку на палиндром, включая технику расширения вокруг центра
«Кодирование строк, разворот и палиндромы» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Разворот строки на месте
Строки Python неизменяемы, поэтому разворот «на месте» означает преобразование в список символов, обмен элементов с помощью двух указателей и последующее объединение. Классический обмен с двумя указателями: поместите left на индекс 0, а right — на последний индекс; меняйте символы местами и сдвигайте указатели к центру, пока они не пересекутся. Временная сложность — O(n), а дополнительная память для списка символов — O(n) (это неизбежно, поскольку строки неизменяемы).
def reverse_string(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
return ''.join(chars)
print(reverse_string('hello')) # 'olleh'
print(reverse_string('Hannah')) # 'hannaH'
# Pythonic shortcut (creates new string):
print('hello'[::-1]) # 'olleh'Разворот слов в предложении
Измените порядок слов, удалив лишние пробелы. Чистое решение на Python: split (обрабатывает несколько пробелов), reverse списка, join. Для разворота на месте массива символов: сначала разверните весь массив, затем разверните каждое отдельное слово. Этот двухпроходный подход работает за O(n) времени и требует O(n) памяти (для строк Python это неизбежно, поскольку они неизменяемы).
def reverse_words(s):
words = s.split() # split and strip whitespace
words.reverse() # in-place reverse
return ' '.join(words) # single space between words
print(reverse_words(' hello world ')) # 'world hello'
print(reverse_words('a good example')) # 'example good a'
# One-liner:
print(' '.join(' hello world '.split()[::-1]))Простая проверка на палиндром
Строка является палиндромом, если она равна своему развороту. Самая быстрая проверка в Python: s == s[::-1]. Для палиндромов без учёта регистра, содержащих только буквенно-цифровые символы (самый распространённый вариант на собеседованиях), сначала нормализуйте строку: отфильтруйте небуквенно-цифровые символы и преобразуйте оставшиеся в нижний регистр, затем сравните. Оба подхода работают за O(n).
def is_palindrome(s):
# Filter and normalise
cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # False
print(is_palindrome('Was it a car or a cat I saw?')) # TrueПроверка на палиндром с помощью двух указателей
Чтобы использовать O(1) дополнительной памяти, проверяйте палиндром с помощью двух указателей, а не среза. Поместите left в позицию 0, а right — в конец. Пропускайте небуквенно-цифровые символы, сравнивайте остальные символы без учёта регистра и при несовпадении возвращайте ложное значение. Этот подход более многословен, но полностью избегает создания очищенной строки — что важно при ограниченной памяти.
def is_palindrome_twoptr(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1; right -= 1
return True
print(is_palindrome_twoptr('A man, a plan, a canal: Panama')) # TrueРасширение от центра для поиска самого длинного палиндрома
Метод расширения от центра находит самую длинную палиндромную подстроку за O(n²) времени и с O(1) дополнительной памятью. Для каждого символа (палиндромы нечётной длины) и каждого промежутка между символами (палиндромы чётной длины) расширяйтесь наружу, пока символы совпадают. Сохраняйте лучшую из найденных пар (начало, конец). Всего имеется 2n-1 центров, а в худшем случае каждое расширение занимает O(n).
def longest_palindrome(s):
best_start = best_end = 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1; right += 1
return left + 1, right - 1 # last valid bounds
for i in range(len(s)):
l, r = expand(i, i) # odd-length
if r - l > best_end - best_start:
best_start, best_end = l, r
l, r = expand(i, i + 1) # even-length
if r - l > best_end - best_start:
best_start, best_end = l, r
return s[best_start:best_end+1]
print(longest_palindrome('babad')) # 'bab' or 'aba'
print(longest_palindrome('cbbd')) # 'bb'Предварительное знакомство с алгоритмом manacher
Алгоритм manacher находит самую длинную палиндромную подстроку за O(n), используя наблюдение, что палиндром внутри более крупного палиндрома можно инициализировать по зеркальной позиции. На собеседованиях редко просят реализовать этот алгоритм, но полезно знать о его существовании. Большинство интервьюеров принимают подход расширения от центра за O(n²) как «достаточно оптимальный» — если попросят продолжение, упомяните алгоритм manacher как теоретическое решение за O(n).
# Manacher's: O(n) longest palindromic substring
def manacher(s):
# Transform s into '#a#b#a#' to handle even/odd uniformly
t = '#' + '#'.join(s) + '#'
n = len(t)
P = [0] * n # P[i] = palindrome radius at i
center = right = 0
for i in range(n):
mirror = 2 * center - i
if i < right:
P[i] = min(right - i, P[mirror])
while (i + P[i] + 1 < n and i - P[i] - 1 >= 0
and t[i+P[i]+1] == t[i-P[i]-1]):
P[i] += 1
if i + P[i] > right:
center, right = i, i + P[i]
max_len = max(P)
center_idx = P.index(max_len)
start = (center_idx - max_len) // 2
return s[start:start+max_len]
print(manacher('babad')) # 'bab'Кодирование длин серий
Кодирование длин серий (RLE) сжимает последовательности одинаковых символов: 'aaabbc' превращается в 'a3b2c1'. Реализация: просматривайте строку с помощью быстрого указателя, чтобы найти конец каждой серии, записывайте символ и его количество в выходной список, затем объединяйте элементы. Для коротких серий входная строка может оказаться короче закодированного результата — перед возвратом всегда проверяйте, стал ли закодированный вариант короче.
def encode_rle(s):
if not s: return ''
parts = []
i = 0
while i < len(s):
char = s[i]
j = i
while j < len(s) and s[j] == char:
j += 1
count = j - i
parts.append(char + (str(count) if count > 1 else ''))
i = j
encoded = ''.join(parts)
return encoded if len(encoded) < len(s) else s
print(encode_rle('aaabbc')) # 'a3b2c'
print(encode_rle('abc')) # 'abc' (no compression gain)Декодирование строк, закодированных с помощью RLE
Декодирование RLE считывает символы и следующие за ними последовательности цифр, разворачивая каждую серию. На собеседованиях иногда предлагают вариант LeetCode, в котором кодирование использует k[encoded_string] для повторяющихся подстрок: например, 3[ab] → ababab. Для этого вложенного варианта требуется стек, чтобы обрабатывать несколько уровней вложенности.
def decode_rle(s):
result = []
i = 0
while i < len(s):
char = s[i]; i += 1
num_str = ''
while i < len(s) and s[i].isdigit():
num_str += s[i]; i += 1
count = int(num_str) if num_str else 1
result.append(char * count)
return ''.join(result)
print(decode_rle('a3b2c')) # 'aaabbc'
print(decode_rle('a2b3c1')) # 'aabbbc'
# Nested bracket decode (LeetCode 394)
def decode_bracket(s):
stack = []
for c in s:
if c != ']':
stack.append(c)
else:
chars = []
while stack[-1] != '[':
chars.append(stack.pop())
stack.pop() # remove '['
k = int(stack.pop())
stack.append(''.join(reversed(chars)) * k)
return ''.join(stack)
print(decode_bracket('3[ab]')) # 'ababab'Проверка палиндрома II: допускается одно удаление
Для данной строки верните истину, если её можно превратить в палиндром, удалив не более одного символа. Используйте два указателя; при первом несовпадении проверьте, является ли палиндромом s[left+1:right+1] или s[left:right] (то есть попробуйте пропустить каждый из несовпадающих символов). Если одна из сторон является палиндромом, верните истину. Этот жадный подход работает, поскольку пропуск несовпадающего символа — единственное полезное действие.
def valid_palindrome(s):
def is_pal(l, r):
while l < r:
if s[l] != s[r]: return False
l += 1; r -= 1
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# Try skipping either character
return is_pal(left+1, right) or is_pal(left, right-1)
left += 1; right -= 1
return True
print(valid_palindrome('aba')) # True
print(valid_palindrome('abca')) # True (delete 'c')
print(valid_palindrome('abc')) # FalseРазбиение на палиндромы I
Разбейте строку на все подстроки, являющиеся палиндромами. Используйте поиск с возвратом: на каждом шаге перебирайте все префиксы оставшейся строки; если префикс является палиндромом, рекурсивно обработайте остаток. Заранее вычислите двумерную логическую таблицу is_pal[i][j] с помощью интервальной DP, чтобы проверки на палиндром занимали O(1), сократив общую сложность поиска с возвратом с O(n² × 2^n) до O(n × 2^n) — это приемлемо, поскольку генерация всех разбиений по своей природе имеет экспоненциальную сложность.
def partition(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
dp[i][i] = True
for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = length == 2 or dp[i+1][j-1]
result = []
def backtrack(start, path):
if start == n: result.append(path[:]); return
for end in range(start, n):
if dp[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition('aab')) # [['a','a','b'],['aa','b']]Кратчайший палиндром: хеширование строки
Найдите самый короткий палиндром, который можно получить, добавляя символы в начало строки. Ключевая идея: найдите самый длинный палиндромный префикс строки s, затем добавьте в начало разворот оставшегося суффикса. Чтобы эффективно найти самый длинный палиндромный префикс, примените функцию отказов KMP к строке s + '#' + reverse(s). Последнее значение функции отказов даёт длину самого длинного палиндромного префикса.
def shortest_palindrome(s):
rev = s[::-1]
combined = s + '#' + rev # '#' prevents overlap
n = len(combined)
kmp = [0] * n
j = 0
for i in range(1, n):
while j > 0 and combined[i] != combined[j]:
j = kmp[j-1]
if combined[i] == combined[j]:
j += 1
kmp[i] = j
# kmp[-1] = length of longest palindromic prefix
to_add = rev[:len(s) - kmp[-1]]
return to_add + s
print(shortest_palindrome('aacecaaa')) # 'aaacecaaa'
print(shortest_palindrome('abcd')) # 'dcbabcd'Быстрая проверка
Проверьте своё понимание понятий «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке вы узнали: проверка палиндрома с двумя указателями выполняется за O(n) времени и использует O(1) памяти — при ограниченной памяти всегда предпочитайте проверки по индексам созданию обратной копии, расширение от центра находит самую длинную палиндромную подстроку за O(n²), рассматривая каждую из 2n-1 позиций как возможный центр палиндрома, а кодирование длин серий сжимает последовательности повторяющихся символов за O(n), тогда как для декодирования вложенного варианта со скобками требуется стек. Далее мы рассмотрим сортировку пузырьком и сортировку вставками.
Часто задаваемые вопросы
Урок «Кодирование строк, разворот и палиндромы» бесплатный?
Да — полный текст урока «Кодирование строк, разворот и палиндромы» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Кодирование строк, разворот и палиндромы»?
Реализуйте разворот слов на месте, кодирование длин серий и проверку на палиндром, включая технику расширения вокруг центра Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Кодирование строк, разворот и палиндромы»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- API строк Python для собеседований
- Скользящее окно для подстрок
- Анаграммы и карты частот символов
- Кодирование строк, разворот и палиндромы