Kodowanie ciągów, odwracanie i palindromy
Zaimplementują Państwo odwracanie słów w miejscu, kodowanie długości serii oraz wykrywanie palindromów, w tym technikę rozszerzania wokół środka.
Kodowanie ciągów, odwracanie i palindromy to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Odwracanie napisu w miejscu
Napisy w Pythonie są niezmienne, więc odwracanie ich „w miejscu” oznacza konwersję na listę znaków, zamianę elementów za pomocą dwóch wskaźników i ponowne połączenie znaków. Klasyczna zamiana z użyciem dwóch wskaźników wygląda tak: ustaw left na indeksie 0, a right na ostatnim indeksie; zamieniaj znaki i przesuwaj wskaźniki do środka, aż się przetną. Złożoność czasowa wynosi O(n), a pamięciowa O(n) ze względu na listę znaków (jest to nieuniknione, ponieważ napisy są niezmienne).
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'Odwracanie słów w zdaniu
Odwróć kolejność słów w zdaniu, usuwając nadmiarowe spacje. Przejrzyste rozwiązanie w Pythonie: podziel napis za pomocą split (obsługuje wiele spacji), odwróć listę i połącz jej elementy za pomocą join. W przypadku odwracania w miejscu tablicy znaków odwróć najpierw całą tablicę, a następnie każde pojedyncze słowo. To dwuprzebiegowe podejście działa w czasie O(n) i wymaga O(n) pamięci (jest to nieuniknione w przypadku napisów w Pythonie, ponieważ są one niezmienne).
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]))Wykrywanie palindromów: podstawy
Napis jest palindromem, jeśli jest równy swojemu odwróceniu. Najszybsze sprawdzenie w Pythonie: s == s[::-1]. W przypadku palindromów nieuwzględniających wielkości liter i zawierających wyłącznie znaki alfanumeryczne (najczęstszy wariant na rozmowach technicznych) najpierw znormalizuj napis: odfiltruj znaki niealfanumeryczne i zamień pozostałe na małe litery, a następnie porównaj. Oba podejścia mają złożoność 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?')) # TrueWykrywanie palindromów: dwa wskaźniki
Aby użyć O(1) dodatkowej pamięci, sprawdzaj palindrom za pomocą dwóch wskaźników zamiast wycinania fragmentu napisu. Ustaw left na 0, a right na końcu. Pomijaj znaki niealfanumeryczne, porównuj pozostałe znaki bez uwzględniania wielkości liter i zwróć False w przypadku niezgodności. To rozwiązanie jest bardziej rozbudowane, ale całkowicie unika tworzenia oczyszczonego napisu — co ma znaczenie przy ograniczonej pamięci.
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')) # TrueRozszerzanie od środka dla najdłuższego palindromu
Technika rozszerzania od środka pozwala znaleźć najdłuższy palindromiczny podciąg w czasie O(n²) i przy użyciu O(1) dodatkowej pamięci. Dla każdego znaku (palindromy o nieparzystej długości) oraz każdej przerwy między znakami (palindromy o parzystej długości) rozszerzaj zakres na zewnątrz, dopóki znaki są takie same. Zapamiętuj najlepszą napotkaną parę (start, end). Istnieje 2n-1 środków, a każde rozszerzanie ma w najgorszym przypadku złożoność 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'Podgląd algorytmu Manachera
Algorytm Manachera znajduje najdłuższy palindromiczny podciąg w czasie O(n), wykorzystując spostrzeżenie, że palindrom znajdujący się wewnątrz większego palindromu można zainicjalizować na podstawie pozycji lustrzanej. Rzadko wymaga się jego implementacji na rozmowach technicznych, ale warto wiedzieć o jego istnieniu. Większość osób prowadzących rozmowy akceptuje podejście z rozszerzaniem od środka o złożoności O(n²) jako „wystarczająco optymalne” — jeśli pojawi się pytanie dodatkowe, warto wspomnieć o algorytmie Manachera jako teoretycznym rozwiązaniu 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'Kodowanie długości serii
Kodowanie długości serii (RLE) kompresuje kolejne powtarzające się znaki: 'aaabbc' staje się 'a3b2c1'. Implementacja: przeglądaj napis za pomocą szybkiego wskaźnika, aby znaleźć koniec każdej serii, zapisuj znak i liczbę jego powtórzeń na liście wynikowej, a następnie połącz elementy. Dla krótkich serii dane wejściowe mogą być krótsze niż wynik kodowania — przed zwróceniem wyniku zawsze sprawdź, czy wersja zakodowana jest krótsza.
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)Dekodowanie napisów zakodowanych metodą RLE
Dekodowanie RLE polega na odczytywaniu znaków i następujących po nich sekwencji cyfr oraz rozwijaniu każdej serii. W zadaniach rekrutacyjnych czasami pojawia się wariant z LeetCode, w którym kodowanie wykorzystuje k[encoded_string] do powtarzania podciągów: na przykład 3[ab] → ababab. Ten zagnieżdżony wariant wymaga stosu do obsługi wielu poziomów zagnieżdżenia.
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'Poprawny palindrom II: dozwolone jedno usunięcie
Dla danego napisu zwróć True, jeśli można uzyskać palindrom, usuwając co najwyżej jeden znak. Użyj dwóch wskaźników; przy pierwszej niezgodności sprawdź, czy s[left+1:right+1] lub s[left:right] jest palindromem (czyli spróbuj pominąć każdy z niepasujących znaków). Jeśli którykolwiek z powstałych fragmentów jest palindromem, zwróć True. To zachłanne podejście działa, ponieważ pominięcie niepasującego znaku jest jedynym użytecznym działaniem.
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')) # FalsePodział na palindromy I
Podziel napis na wszystkie możliwe części będące palindromami. Użyj metody nawrotów: na każdym etapie wypróbuj wszystkie prefiksy pozostałej części napisu; jeśli prefiks jest palindromem, wywołaj rekurencję dla reszty. Wstępnie oblicz dwuwymiarową tablicę wartości logicznych is_pal[i][j] za pomocą programowania dynamicznego po przedziałach, aby sprawdzanie palindromu miało złożoność O(1). Zmniejsza to ogólną złożoność metody nawrotów z O(n² × 2^n) do O(n × 2^n) — jest to akceptowalne, ponieważ generowanie wszystkich podziałów ma z natury wykładniczą złożoność.
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']]Najkrótszy palindrom: haszowanie napisów
Znajdź najkrótszy palindrom, który można uzyskać, dodając znaki na początku napisu. Kluczowa obserwacja: znajdź najdłuższy palindromiczny prefiks s, a następnie dodaj na początku odwrócony pozostały sufiks. Aby efektywnie znaleźć najdłuższy palindromiczny prefiks, użyj funkcji niepowodzeń algorytmu KMP dla napisu s + '#' + reverse(s). Ostatnia wartość funkcji niepowodzeń podaje długość najdłuższego palindromicznego prefiksu.
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'Szybki test
Proszę sprawdzić swoje zrozumienie koncepcji Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: wykrywanie palindromu za pomocą dwóch wskaźników ma złożoność czasową O(n) i pamięciową O(1) — gdy liczy się pamięć, należy zawsze wybierać sprawdzanie na podstawie indeksów zamiast tworzenia odwróconej kopii, rozszerzanie od środka znajduje najdłuższy palindromiczny podciąg w czasie O(n²), traktując każdą z 2n-1 pozycji jako potencjalny środek palindromu oraz kodowanie długości serii kompresuje kolejne serie w czasie O(n), a dekodowanie wymaga stosu w wariancie z zagnieżdżonymi nawiasami. W następnej kolejności omówimy sortowanie bąbelkowe i sortowanie przez wstawianie.
Często zadawane pytania
Czy lekcja „Kodowanie ciągów, odwracanie i palindromy” jest bezpłatna?
Tak — pełny tekst „Kodowanie ciągów, odwracanie i palindromy” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Kodowanie ciągów, odwracanie i palindromy”?
Zaimplementują Państwo odwracanie słów w miejscu, kodowanie długości serii oraz wykrywanie palindromów, w tym technikę rozszerzania wokół środka. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Kodowanie ciągów, odwracanie i palindromy”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Python String API na rozmowach rekrutacyjnych
- Okno przesuwne dla podciągów
- Anagramy i mapy częstotliwości znaków
- Kodowanie ciągów, odwracanie i palindromy