Pisin yhteinen alijono
Määritelkää kahden merkkijonon LCS-rekurrenssi, täyttäkää kaksiulotteinen taulukko ja palauttakaa varsinainen alijono jäljittämällä taulukkoa taaksepäin.
Pisin yhteinen alijono on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mikä on alijono?
Alijono muodostetaan merkkijonosta poistamalla joitakin merkkejä (tai jättämällä kaikki merkit paikoilleen) muuttamatta jäljelle jäävien merkkien järjestystä. Esimerkiksi 'ACE' on merkkijonon 'ABCDE' alijono, mutta 'AEC' ei ole, koska järjestys rikkoutuu. Kahden merkkijonon pisin yhteinen alijono (LCS) on pisin alijono, joka esiintyy molemmissa. Merkkijonoilla 'ABCBDAB' ja 'BDCABA' on yhteinen LCS 'BCBA' tai 'BDAB', jonka pituus on 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)) # TrueLCS:n rekurrenssin johtaminen
Määritellään dp[i][j] = merkkijonojen text1[:i] ja text2[:j] pisimmän yhteisen alijonon pituus. Jos merkit täsmäävät (text1[i-1] == text2[j-1]), LCS:ää jatketaan yhdellä merkillä: dp[i][j] = dp[i-1][j-1] + 1. Jos merkit eivät täsmää, valitaan parempi vaihtoehto jättämällä merkki pois jommastakummasta merkkijonosta: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Perustapaus: dp[0][j] = dp[i][0] = 0 (tyhjän merkkijonon kanssa yhteisen alijonon pituus on 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')) # 2LCS-taulukon seuraaminen
Kun text1='ABCD' ja text2='ACBD': aloittakaa pelkillä nollilla. Kun merkit täsmäävät (A–A, C–C, B–B, jos ne ovat oikeassa kohdassa, D–D), dp[i][j] = dp[i-1][j-1] + 1. Muussa tapauksessa valitaan vasemman- ja yläpuolisen naapurin maksimi. Täytetyn taulukon läpikäynti osoittaa, kuinka diagonaaliset siirtymät vastaavat toisiaan vastaavia merkkejä. Lopullinen arvo dp[4][4] antaa LCS:n pituuden.
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')Todellisen LCS:n rekonstruointi
Palauttaaksesi varsinaisen LCS-merkkijonon käy DP-taulukkoa taaksepäin kohdasta dp[m][n]. Jos text1[i-1] == text2[j-1], tämä merkki kuuluu LCS:ään — tallenna se ja siirry vinosti kohtaan (i-1, j-1). Jos dp[i-1][j] > dp[i][j-1], siirry ylös; muussa tapauksessa siirry vasemmalle. Käännä kerätyt merkit lopuksi, koska etenit taaksepäin. Tämä rekonstruktio toimii ajassa 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 BDABTilankäytön optimointi O(n):ään
LCS-taulukossa tarvitaan vain nykyinen ja edellinen rivi. Voitte käyttää kooltaan n+1 olevaa yksiulotteista taulukkoa ja muuttujaa diagonal tallentamaan arvon, joka oli kohdassa dp[i-1][j-1] ennen sen päällekirjoittamista. Käykää jokainen rivi läpi vasemmalta oikealle. Jokaisen solun jälkeen päivitetty dp[j] sisältää nykyisen rivin arvon, ja tallentakaa edellinen arvo muuttujaan diagonal ennen sen päällekirjoittamista.
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')) # 4LCS:n ja muokkausetäisyyden välinen yhteys
LCS liittyy läheisesti muokkausetäisyyteen (Levenshteinin etäisyyteen). Jos tunnette LCS:n, voitte laskea pienimmän muokkausetäisyyden käyttämällä vain lisäys- ja poisto-operaatioita: edit_dist = m + n - 2 * LCS(s1, s2). Jokainen s1:n merkki, joka ei kuulu LCS:ään, on poistettava, ja jokainen s2:n merkki, joka ei kuulu LCS:ään, on lisättävä. Korvausta ei lasketa tässä, koska sallimme vain lisäykset ja poistot, mutta kaava on hyödyllinen samankaltaisissa ongelmissa.
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')) # 5Kahden merkkijonon poistotoiminto
Kahden merkkijonon poistotoiminto (LeetCode 583) kysyy, mikä on pienin poistojen määrä, jolla kaksi merkkijonoa saadaan samoiksi. Säilytettävien merkkien on muodostettava yhteinen alijono, joten LCS kannattaa maksimoida ja kaikki muu poistaa. Vastaus: m + n - 2 * LCS(s1, s2). Tämä vastaa edellä kuvattua lisäys- ja poisto-operaatioihin perustuvaa muokkausetäisyyttä. Ongelman muotoileminen LCS:n avulla on tehokas pelkistystekniikka.
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')) # 4Pisin yhteinen osajono
Älkää sekoittako käsitteitä LCS (alijono) ja pisin yhteinen osajono. Osajono on yhtenäinen, joten jos merkit eivät täsmää, lukumäärä palautetaan arvoon 0 sen sijaan, että naapurien maksimi otettaisiin. Rekurrenssi muuttuu muotoon: jos merkit täsmäävät, dp[i][j] = dp[i-1][j-1] + 1; muussa tapauksessa dp[i][j] = 0. Seuratkaa kaikkien solujen joukosta suurinta havaittua arvoa.
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 sekvenssien vertailuun
LCS:ää käytetään laajasti erotustyökaluissa (kuten Unix-komennossa diff) tiedostojen vertailuun. Kahden tiedoston välinen muokkauskomentosarja johdetaan LCS:stä: LCS:ään kuuluvat rivit ovat muuttumattomia, tiedostosta 1 puuttuvat ylimääräiset rivit poistetaan ja tiedostossa 2 olevat ylimääräiset rivit lisätään. LCS:n ymmärtäminen auttaa hahmottamaan, miten versionhallintajärjestelmät seuraavat muutoksia ja miksi yhdistämisristiriitoja syntyy.
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)Lyhin yhteinen supersekvenssi
Lyhin yhteinen supersekvenssi (LeetCode 1092) tarkoittaa lyhintä merkkijonoa, jossa sekä s1 että s2 ovat alijonoina. Jokainen LCS:n merkki esiintyy supersekvenssissä kerran; molempien merkkijonojen LCS:ään kuulumattomat merkit on sisällytettävä siihen. Pituus = m + n - LCS(s1, s2). Rekonstruointi tehdään käymällä LCS:n tavoin taaksepäin, mutta lisäämällä kummankin merkkijonon merkit kohdissa, joissa ne eivät täsmää.
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 5LCS:n aikavaativuus ja haastatteluvinkit
Tavanomainen LCS-algoritmi toimii ajassa O(m×n) ja tilassa O(m×n), mutta tilankäyttö voidaan pienentää arvoon O(min(m,n)) liukuvan taulukon avulla. Tärkeitä haastatteluvinkkejä: (1) Määrittele selkeästi DP-tilan merkitys ennen koodaamista. (2) Käsittele osuma- ja ei-osumatapaukset erikseen. (3) Kun tehtävässä pyydetään rekonstruoimaan sekvenssi, kuvaile taaksepäin eteneminen ennen sen koodaamista. (4) Mainitse pisin kasvava alijono (LIS) siihen liittyvänä yksiulotteisena ongelmana, joka voidaan ratkaista ajassa O(n log n) patience sorting -menetelmällä.
# 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)Pikatarkistus
Testatkaa tämän oppitunnin käsitteiden ymmärrystänne: Data Structures & Algorithms — Coding Interview Prep.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että LCS käyttää osumassa kaavaa dp[i][j] = dp[i-1][j-1]+1 ja muulloin arvoa max(dp[i-1][j], dp[i][j-1]), varsinainen sekvenssi rekonstruoidaan etenemällä osumissa vinosti taaksepäin ja eroissa kohti suurempaa naapuriarvoa ja LCS toimii muokkausetäisyyden, poistotoimintojen, lyhimmän yhteisen supersekvenssin ja erotustyökalujen perustana. Seuraavaksi johdamme muokkausetäisyyden (Levenshteinin etäisyyden) rekurrenssin, joka lisää korvaukset LCS-kehykseen.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Pisin yhteinen alijono” ilmainen?
Kyllä – oppitunnin ”Pisin yhteinen alijono” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Pisin yhteinen alijono”?
Määritelkää kahden merkkijonon LCS-rekurrenssi, täyttäkää kaksiulotteinen taulukko ja palauttakaa varsinainen alijono jäljittämällä taulukkoa taaksepäin. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Pisin yhteinen alijono”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Yksikäsitteiset polut ja pienin polkusumma ruudukoissa
- Pisin yhteinen alijono
- Muokkausetäisyys (Levenshtein)
- Kaksiulotteisen DP:n tilan optimointi