Pisin palindrominen alijono ja osajono
Soveltakaa väli-DP:tä pisimmän palindromisen alijonon etsimiseen ja keskeltä laajentamisen menetelmää pisimmän palindromisen osajonon etsimiseen.
Pisin palindrominen alijono ja osajono 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.
Palindromimääritelmät kerrattuna
Palindrominen alijono on alijono (jonka alkiot eivät välttämättä ole peräkkäisiä), joka luetaan samoin etu- ja takaperin. Palindromisen osamerkkijonon merkkien on oltava peräkkäisiä. Merkkijonossa 'bbbab' pisin palindrominen alijono on 'bbbb' (pituus 4), kun taas pisin palindrominen osamerkkijono on 'bbb' (pituus 3). Nämä kaksi ongelmaa edellyttävät eri tekniikoita samankaltaisista nimistään huolimatta.
Pisin palindrominen alijono: LPS-tila
Määritellään dp[i][j] pisimmän palindromisen alijonon pituudeksi merkkijonon s[i..j] alueella. Rekurenssi on seuraava: jos s[i] == s[j], niin dp[i][j] = dp[i+1][j-1] + 2 (kaksi samaa reunamerkkiä laajentavat sisempää palindromia). Muussa tapauksessa dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (ohitetaan vasen tai oikea merkki). Perustapaus: dp[i][i] = 1 kaikille yksittäisille merkeille.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')LPS-taulukon täyttöjärjestys ja toteutus
Täytämme LPS-taulukon kasvavan välin pituuden mukaan samalla tavalla kuin yleisessä interval DP:ssä. Jokaisella vähintään 2 merkin pituisella välillä [i, j] tarkistamme, ovatko kaksi reunamerkkiä samat, ja sovellamme rekurenssia. Lopullinen vastaus on dp[0][n-1], eli koko merkkijonon LPS.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4LPS:n ja LCS:n vastaavuus
Tyylikäs vaihtoehto: merkkijonon s LPS on sama kuin merkkijonon s ja sen käänteisen merkkijonon s[::-1] LCS. Tämä johtuu siitä, että jokainen merkkijonon s palindrominen alijono on merkkijonon s ja sen käänteisen merkkijonon yhteinen alijono. Näin voitte käyttää LCS-koodianne suoraan uudelleen. Merkkijono 'bbbab' käännettynä on 'babbb', ja niiden LCS:n pituus on 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[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]
print(lps_via_lcs('bbbab')) # 4Pisin palindrominen osamerkkijono: brute force
Pisin palindrominen osamerkkijono edellyttää, että merkit ovat peräkkäisiä. Brute force -menetelmä tarkistaa kaikki O(n²) osamerkkijonot ja varmistaa jokaisen palindromisuuden ajassa O(n), joten kokonaisaikavaativuus on O(n³). On olemassa kaksi nopeampaa lähestymistapaa: interval DP, jonka aika- ja tilavaativuus ovat O(n²), sekä keskipisteen ympärille laajentaminen, jonka aikavaativuus on O(n²) ja tilavaativuus O(1). Haastatteluissa keskipisteen ympärille laajentamista suositaan, koska sen vakiokerroin on pienempi ja koodi selkeämpää.
Palindromisen osamerkkijonon interval DP
Määritellään dp[i][j] = True, jos s[i..j] on palindromi. Rekurenssi: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Perustapaukset: dp[i][i] = True ja dp[i][i+1] = (s[i] == s[i+1]). Seurataan löydetyn pisimmän palindromin pituutta. Taulukko täytetään kasvavan pituuden mukaan. Aikavaativuus on O(n²) ja tilavaativuus O(n²).
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'Keskipisteen ympärille laajentamisen tekniikka
Keskipisteen ympärille laajentamisen menetelmässä jokaista merkkiä ja jokaista vierekkäisten merkkien paria kokeillaan mahdollisena palindromin keskikohtana, minkä jälkeen laajennutaan ulospäin niin kauan kuin molemmat puolet täsmäävät. Mahdollisia keskikohtia on 2n-1 (n parittoman pituista ja n-1 parillisen pituista). Kukin laajennus vie enintään O(n) aikaa, joten kokonaisaikavaativuus on O(n²) ja tilavaativuus O(1) — tämä on useimmissa haastattelutilanteissa optimaalinen ratkaisu.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'LPS:n tilan optimointi
LPS:n interval DP käyttää tilaa O(n²). Kun tarvitsette vain pituuden ettekä itse alijonoa, tilankäyttöä voi pienentää huomaamalla, että dp[i][j] riippuu vain arvoista dp[i+1][j-1], dp[i+1][j] ja dp[i][j-1]. Käyttämällä rivejä uudelleen ja tallentamalla yhden diagonaaliarvon voitte saavuttaa tilavaativuuden O(n) — toteutus on kuitenkin monimutkaisempi, ja haastatteluissa tätä tarvitaan harvoin.
LPS:n rekonstruointi
Palindromisen alijonon rekonstruoimiseksi jäljittäkää kulku takaisin DP-taulukon läpi. Aloittakaa kohdasta (0, n-1). Jos s[i] == s[j], lisätkää kyseinen merkki tuloksen molempiin päihin ja siirtykää kohtaan (i+1, j-1). Muussa tapauksessa siirtykää siihen kohdista (i+1, j) ja (i, j-1), jonka arvo on suurempi. Tällä ahneella takaisinjäljityksellä saadaan yksikäsitteisesti rekonstruoitua yksi optimaalinen palindrominen alijono.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')LPS:n ja LCS:n aikavaativuuden vertailu
Sekä interval DP:llä ratkaistavan LPS:n että LCS:n aikavaativuus on O(n²) ja tilavaativuus O(n²). Pisimpiin palindromisiin osamerkkijonoihin käytettävän keskipisteen ympärille laajentamisen aikavaativuus on O(n²), mutta tilavaativuus vain O(1). Manacherin algoritmi ratkaisee osamerkkijono-ongelman ajassa O(n) ja tilassa O(n), mutta se on niin monimutkainen, että haastattelijat harvoin odottavat sen tuntemista. Useimmissa haastattelutilanteissa keskipisteen ympärille laajentaminen on osamerkkijonoversion odotettu optimaalinen ratkaisu.
Yleiset sudenkuopat ja reunatapaukset
Varokaa näitä sudenkuoppia: (1) alijonon ja osamerkkijonon sekoittaminen — kyseessä ovat eri ongelmat, joihin on eri ratkaisut; (2) pituudeltaan 2 olevien intervallien väli-DP:n perustapaus vaatii erityiskäsittelyn, koska dp[i+1][j-1] olisi dp[i+1][i] (tyhjä intervalli); (3) käyttäkää expand-around-centre-menetelmässä alustavaa arvoa max_len = 1 (jokainen yksittäinen merkki on palindromi); ja (4) tulosta poimiessanne laskekaa start = i - (best-1)//2, jotta aloitusindeksi löytyy oikein keskipisteen perusteella.
Pikatesti
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteiden ymmärtämistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että LPS käyttää väli-DP:tä ja rekurrenssia dp[i][j] = dp[i+1][j-1]+2, kun merkit täsmäävät, pisin palindrominen osamerkkijono kannattaa ratkaista expand-around-centre-menetelmällä ajassa O(n²) ja tilassa O(1) ja LPS on sama kuin merkkijonon ja sen käänteisen merkkijonon LCS. Seuraavaksi käsittelemme palindromeihin osiointia II, jossa yhdistyvät palindromitaulukko ja yksiulotteinen DP leikkausten vähimmäismäärän laskemiseen.
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 palindrominen alijono ja osajono” ilmainen?
Kyllä – oppitunnin ”Pisin palindrominen alijono ja osajono” 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 palindrominen alijono ja osajono”?
Soveltakaa väli-DP:tä pisimmän palindromisen alijonon etsimiseen ja keskeltä laajentamisen menetelmää pisimmän palindromisen osajonon etsimiseen. 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 palindrominen alijono ja osajono”-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
- Väli-DP:n malli ja täyttöjärjestys
- Pisin palindrominen alijono ja osajono
- Palindrome Partitioning II
- Burst Balloons: käänteinen väli-DP