Najdłuższy wspólny podciąg
Zdefiniują Państwo rekurencję LCS dla dwóch ciągów, wypełnią dwuwymiarową tablicę i odtworzą właściwy podciąg, cofając się po tablicy.
Najdłuższy wspólny podciąg to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Czym jest podciąg
Podciąg napisu powstaje przez usunięcie niektórych znaków (lub żadnego z nich) bez zmiany kolejności pozostałych znaków. Na przykład 'ACE' jest podciągiem 'ABCDE', ale 'AEC' nim nie jest (kolejność została zmieniona). Longest Common Subsequence (LCS) dwóch napisów to najdłuższy podciąg występujący w obu z nich. Napisy 'ABCBDAB' i 'BDCABA' mają wspólny LCS 'BCBA' lub 'BDAB' o długości 4.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueWyprowadzenie rekurencji LCS
Zdefiniuj dp[i][j] jako długość LCS dla text1[:i] i text2[:j]. Jeśli znaki są takie same (text1[i-1] == text2[j-1]), wydłużamy LCS o 1: dp[i][j] = dp[i-1][j-1] + 1. Jeśli znaki się nie zgadzają, wybieramy lepszy wynik, pomijając znak z jednego z napisów: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Przypadek bazowy: dp[0][j] = dp[i][0] = 0 (LCS pustego napisu ma długość 0).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2Śledzenie tabeli LCS
Dla text1='ABCD' i text2='ACBD': należy rozpocząć od samych zer. Gdy znaki się zgadzają (A-A, C-C, B-B, jeśli znajdują się we właściwych pozycjach, D-D), dp[i][j] = dp[i-1][j-1] + 1. W przeciwnym razie należy wybrać maksimum z sąsiednich wartości po lewej i u góry. Przeglądanie wypełnionej tabeli pokazuje, że kroki po przekątnej odpowiadają dopasowanym znakom. Końcowa wartość dp[4][4] określa długość LCS.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')Odtwarzanie właściwego LCS
Aby odtworzyć właściwy napis LCS, prześledź wstecz tabelę DP od dp[m][n]. Jeśli text1[i-1] == text2[j-1], ten znak należy do LCS — zapisz go i przejdź po skosie do (i-1, j-1). Jeśli dp[i-1][j] > dp[i][j-1], przejdź w górę; w przeciwnym razie w lewo. Na końcu odwróć zebrane znaki, ponieważ przechodzisz tabelę wstecz. Odtwarzanie działa w czasie O(m+n).
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABOptymalizacja pamięci do O(n)
Tabela LCS wymaga tylko bieżącego i poprzedniego wiersza. Możesz użyć tablicy 1D o rozmiarze n+1 oraz zmiennej diagonal do przechowywania wartości, która znajdowała się w dp[i-1][j-1] przed jej nadpisaniem. W każdym wierszu iteruj od lewej do prawej. Po przetworzeniu każdej komórki zaktualizowane dp[j] przechowuje wartość bieżącego wiersza, a poprzednią wartość zapisujesz w diagonal przed jej nadpisaniem.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4Związek między LCS a odległością edycyjną
LCS jest ściśle powiązany z odległością edycyjną (odległością Levenshteina). Jeśli znasz LCS, możesz obliczyć minimalną odległość edycyjną, używając wyłącznie wstawiania i usuwania: edit_dist = m + n - 2 * LCS(s1, s2). Każdy znak z s1, który nie należy do LCS, wymaga usunięcia, a każdy znak z s2, który nie należy do LCS, wymaga wstawienia. Zastępowanie nie jest tutaj uwzględniane, ponieważ dozwolone są tylko operacje wstawiania i usuwania, ale ten wzór jest przydatny w pokrewnych problemach.
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5Operacja usuwania dla dwóch napisów
Operacja usuwania dla dwóch napisów (LeetCode 583) polega na znalezieniu minimalnej liczby usunięć potrzebnych, aby dwa napisy stały się identyczne. Pozostawione znaki muszą tworzyć wspólny podciąg, dlatego należy maksymalizować LCS i usunąć wszystkie pozostałe znaki. Odpowiedź: m + n - 2 * LCS(s1, s2). Jest to równoważne opisanej wyżej odległości edycyjnej z operacjami wstawiania i usuwania. Formułowanie problemów w kategoriach LCS to skuteczna technika redukcji.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4Najdłuższy wspólny podłańcuch
Nie myl LCS (podciągu) z najdłuższym wspólnym podłańcuchem. Podłańcuch jest spójny, więc gdy znaki się nie zgadzają, licznik jest zerowany do 0 zamiast przyjmować maksimum z sąsiednich wartości. Rekurencja zmienia się na: jeśli znaki są zgodne, dp[i][j] = dp[i-1][j-1] + 1; w przeciwnym razie dp[i][j] = 0. Należy śledzić największą wartość spośród wszystkich komórek.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)LCS w porównywaniu sekwencji
LCS jest powszechnie używany w narzędziach diff (takich jak uniksowy diff) do porównywania plików. Skrypt zmian między dwoma plikami jest wyprowadzany na podstawie LCS: linie należące do LCS pozostają niezmienione, dodatkowe linie z pliku 1 są usuwane, a dodatkowe linie z pliku 2 są wstawiane. Zrozumienie LCS pomaga lepiej pojąć, jak systemy kontroli wersji śledzą zmiany i dlaczego występują konflikty podczas scalania.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)Najkrótszy wspólny nadciąg
Najkrótszy wspólny nadciąg (LeetCode 1092) to najkrótszy napis zawierający zarówno s1, jak i s2 jako podciągi. Każdy znak LCS występuje w nadciągu tylko raz, natomiast znaki nienależące do LCS z obu napisów muszą zostać uwzględnione. Długość = m + n - LCS(s1, s2). Aby go odtworzyć, użyj tego samego przechodzenia wstecz po LCS, ale w pozycjach, w których znaki się nie zgadzają, uwzględnij znaki z obu napisów.
def shortest_common_supersequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5Złożoność LCS i wskazówki rekrutacyjne
Klasyczny algorytm LCS działa w czasie O(m×n) i zajmuje O(m×n) pamięci, którą można zmniejszyć do O(min(m,n)) za pomocą sztuczki z tablicą kroczącą. Najważniejsze wskazówki rekrutacyjne: (1) Przed rozpoczęciem kodowania jasno określ, co reprezentuje stan DP. (2) Rozpatruj osobno przypadki zgodności i braku zgodności znaków. (3) Gdy trzeba odtworzyć sekwencję, najpierw opisz przechodzenie wstecz, a dopiero potem je zakoduj. (4) Wspomnij o najdłuższym rosnącym podciągu (LIS) jako pokrewnym problemie 1D, który można rozwiązać w czasie O(n log n) za pomocą sortowania cierpliwości.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)Szybki test
Sprawdź swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyłeś się, że: LCS używa dp[i][j] = dp[i-1][j-1]+1 dla zgodnych znaków, a w przeciwnym razie max(dp[i-1][j], dp[i][j-1]), rzeczywistą sekwencję odtwarza się, przechodząc po skosie dla zgodnych znaków i w kierunku większego sąsiada dla niezgodnych oraz LCS stanowi podstawę odległości edycyjnej, operacji usuwania, najkrótszego wspólnego nadciągu i narzędzi diff. Następnie wyprowadzimy rekurencję odległości edycyjnej (Levenshteina), która rozszerza schemat LCS o zastępowanie.
Często zadawane pytania
Czy lekcja „Najdłuższy wspólny podciąg” jest bezpłatna?
Tak — pełny tekst „Najdłuższy wspólny podciąg” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Najdłuższy wspólny podciąg”?
Zdefiniują Państwo rekurencję LCS dla dwóch ciągów, wypełnią dwuwymiarową tablicę i odtworzą właściwy podciąg, cofając się po tablicy. Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 2 z 4.
Ile czasu zajmuje lekcja „Najdłuższy wspólny podciąg”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA 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
- Unikalne ścieżki i minimalna suma ścieżki na siatkach
- Najdłuższy wspólny podciąg
- Odległość edycyjna (Levenshteina)
- Optymalizacja pamięci dla dwuwymiarowego DP