Longest Common Subsequence
Definisikan relasi rekurensi LCS untuk dua string, isi tabel 2D, dan rekonstruksi subsekuens sebenarnya dengan menelusuri tabel mundur.
Longest Common Subsequence adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa itu Subsekuens
Subsekuens dari sebuah untaian dibentuk dengan menghapus beberapa karakter (atau tidak menghapus apa pun) tanpa mengubah urutan karakter yang tersisa. Sebagai contoh, 'ACE' adalah subsekuens dari 'ABCDE', tetapi 'AEC' bukan (urutannya tidak sesuai). Subsekuens Bersama Terpanjang (LCS) dari dua untaian adalah subsekuens terpanjang yang muncul pada keduanya. 'ABCBDAB' dan 'BDCABA' memiliki LCS 'BCBA' atau 'BDAB' dengan panjang 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)) # TruePenurunan Relasi Rekurensi LCS
Definisikan dp[i][j] = panjang LCS dari text1[:i] dan text2[:j]. Jika karakternya cocok (text1[i-1] == text2[j-1]), kita memperpanjang LCS sebesar 1: dp[i][j] = dp[i-1][j-1] + 1. Jika tidak cocok, kita mengambil hasil yang lebih baik dengan melewati satu karakter dari salah satu untaian: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Kasus dasar: dp[0][j] = dp[i][0] = 0 (LCS dengan untaian kosong memiliki panjang 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')) # 2Menelusuri Tabel LCS
Untuk text1='ABCD' dan text2='ACBD': Mulailah dengan semua nilai nol. Saat karakter cocok (A-A, C-C, B-B jika berada pada posisi yang benar, D-D), dp[i][j] = dp[i-1][j-1] + 1. Jika tidak, ambil nilai maksimum dari tetangga kiri atau atas. Menelusuri tabel yang telah diisi menunjukkan bagaimana langkah diagonal berkaitan dengan karakter yang cocok. Nilai akhir dp[4][4] memberikan panjang 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')Merekonstruksi LCS Sebenarnya
Untuk mendapatkan kembali teks LCS yang sebenarnya, telusuri tabel DP mundur dari dp[m][n]. Jika text1[i-1] == text2[j-1], karakter ini termasuk dalam LCS — catat karakter tersebut dan bergerak secara diagonal ke (i-1, j-1). Jika dp[i-1][j] > dp[i][j-1], bergerak ke atas; jika tidak, bergerak ke kiri. Balik urutan karakter yang terkumpul pada akhir karena Anda melakukan penelusuran mundur. Rekonstruksi ini berjalan dalam waktu 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 BDABOptimasi Ruang menjadi O(n)
Tabel LCS hanya memerlukan baris saat ini dan baris sebelumnya. Anda dapat menggunakan larik 1D berukuran n+1 dan variabel diagonal untuk menyimpan nilai yang sebelumnya berada di dp[i-1][j-1] sebelum ditimpa. Lakukan iterasi dari kiri ke kanan untuk setiap baris. Setelah setiap sel diproses, dp[j] yang telah diperbarui menyimpan nilai baris saat ini, dan Anda menyimpan nilai sebelumnya dalam diagonal sebelum menimpanya.
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')) # 4Hubungan LCS dan Jarak Edit
LCS berkaitan erat dengan Jarak Edit (jarak Levenshtein). Jika mengetahui LCS, Anda dapat menghitung jarak edit minimum hanya dengan menggunakan penyisipan dan penghapusan: edit_dist = m + n - 2 * LCS(s1, s2). Setiap karakter dari s1 yang tidak terdapat dalam LCS memerlukan satu penghapusan, dan setiap karakter dari s2 yang tidak terdapat dalam LCS memerlukan satu penyisipan. Penggantian tidak dihitung di sini karena kita hanya mengizinkan penyisipan dan penghapusan, tetapi rumus ini berguna untuk masalah terkait.
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')) # 5Operasi Penghapusan untuk Dua Teks
Operasi Penghapusan untuk Dua Teks (LeetCode 583) meminta jumlah minimum penghapusan untuk membuat dua teks menjadi sama. Karakter yang dipertahankan harus membentuk subsekuens umum, jadi Anda ingin memaksimalkan LCS dan menghapus semua karakter lainnya. Jawabannya: m + n - 2 * LCS(s1, s2). Ini setara dengan jarak edit menggunakan penyisipan dan penghapusan di atas. Membingkai masalah dalam istilah LCS merupakan teknik reduksi yang ampuh.
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')) # 4Subrentetan Umum Terpanjang
Jangan keliru membedakan LCS (subsekuens) dengan Subrentetan Umum Terpanjang. Subrentetan bersifat berurutan tanpa terputus, sehingga jika karakter tidak cocok, hitungan diatur ulang menjadi 0, bukan mengambil nilai maksimum dari tetangga. Relasi rekurensinya berubah menjadi: jika karakter cocok, dp[i][j] = dp[i-1][j-1] + 1; jika tidak, dp[i][j] = 0. Lacak nilai maksimum yang terlihat di semua sel.
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 untuk Perbandingan Urutan
LCS banyak digunakan dalam alat diff (seperti diff di Unix) untuk membandingkan berkas. Skrip pengeditan antara dua berkas diturunkan dari LCS: baris dalam LCS tidak berubah, baris tambahan dari berkas 1 dihapus, dan baris tambahan dari berkas 2 disisipkan. Memahami LCS membantu Anda mengapresiasi cara sistem pengendalian versi melacak perubahan dan alasan konflik penggabungan terjadi.
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)Supersekuens Umum Terpendek
Supersekuens Umum Terpendek (LeetCode 1092) meminta teks terpendek yang memiliki s1 dan s2 sebagai subsekuens. Setiap karakter LCS muncul satu kali dalam supersekuens; karakter yang bukan bagian dari LCS dari kedua teks harus disertakan. Panjangnya = m + n - LCS(s1, s2). Untuk merekonstruksinya, gunakan penelusuran mundur LCS yang sama, tetapi sertakan karakter dari kedua teks pada posisi yang tidak cocok.
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 5Kompleksitas LCS dan Kiat Wawancara
Algoritme LCS klasik berjalan dalam waktu O(m×n) dan ruang O(m×n), yang dapat dikurangi menjadi O(min(m,n)) dengan trik larik bergulir. Kiat utama wawancara: (1) Tentukan dengan jelas makna keadaan DP sebelum menulis kode. (2) Tangani kasus cocok dan tidak cocok secara berbeda. (3) Jika diminta merekonstruksi urutan, jelaskan penelusuran mundur sebelum menulis kodenya. (4) Sebutkan Subsekuens Menaik Terpanjang (LIS) sebagai masalah 1D terkait yang dapat diselesaikan dalam O(n log n) dengan pengurutan patience.
# 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)Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: LCS menggunakan dp[i][j] = dp[i-1][j-1]+1 saat cocok, dan max(dp[i-1][j], dp[i][j-1]) jika tidak, urutan sebenarnya direkonstruksi dengan menelusuri mundur secara diagonal saat cocok dan menuju tetangga yang lebih besar saat tidak cocok, serta LCS menjadi dasar jarak edit, operasi penghapusan, supersekuens umum terpendek, dan alat diff. Selanjutnya kita akan menurunkan relasi rekurensi Jarak Edit (Levenshtein), yang menambahkan penggantian ke kerangka LCS.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Longest Common Subsequence” gratis?
Ya — teks lengkap “Longest Common Subsequence” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Longest Common Subsequence”?
Definisikan relasi rekurensi LCS untuk dua string, isi tabel 2D, dan rekonstruksi subsekuens sebenarnya dengan menelusuri tabel mundur. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Longest Common Subsequence” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Jalur Unik dan Jumlah Jalur Minimum pada Grid
- Longest Common Subsequence
- Jarak Edit (Levenshtein)
- Optimasi Ruang untuk DP 2D