Bir string içindeki en uzun palindromik alt diziyi (Longest Palindromic Substring) bulun.
Cevap
En yaygın mülakat çözümü merkezden genişletme (expand around center) yöntemidir: her palindromun bir merkezi vardır ve 2n - 1 olası merkez (tek uzunluk için karakter, çift uzunluk için iki karakter arası) bulunur. Her merkezden iki yöne eşit karakterler bittiği sürece genişleriz.
def longest_palindrome(s: str) -> str:
if len(s) < 2:
return s
start, best = 0, 1
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return l + 1, r - l - 1 # başlangıç, uzunluk
for i in range(len(s)):
for l, r in ((i, i), (i, i + 1)): # tek ve çift merkez
st, length = expand(l, r)
if length > best:
start, best = st, length
return s[start:start + best]
print(longest_palindrome("babad")) # "bab" (veya "aba")
print(longest_palindrome("cbbd")) # "bb"Alternatifler
| Yöntem | Zaman | Bellek |
|---|---|---|
| Brute force (tüm alt diziler) | O(n³) | O(1) |
Dinamik programlama dp[i][j] | O(n²) | O(n²) |
| Merkezden genişletme | O(n²) | O(1) |
| Manacher algoritması | O(n) | O(n) |
Mülakatta merkezden genişletme beklenir; Manacher'ı bildiğinizi söylemek artı puandır ama yazmanız nadiren istenir.
Sık hata
Çift uzunluklu palindromları ("abba") unutmak. Bu yüzden her i için hem (i, i) hem (i, i+1) denenir.
İlgili Algoritmalar & Veri Yapıları soruları
- Binary search'ün zaman karmaşıklığı nedir ve neden?
- Two Sum: toplamı hedefe eşit olan iki elemanın indekslerini bulun.
- Bir parantez dizisinin geçerli olup olmadığını kontrol edin: "({[]})"
- Tek yönlü bağlı listeyi ters çevirin.
- BFS ve DFS arasındaki fark nedir? Hangisini ne zaman kullanırsınız?
- get ve put işlemleri O(1) olan bir LRU Cache tasarlayın.
Bu konuda başka bir soru biliyor musun?
Mülakatta karşılaştığın soruları ekle, onaylandıktan sonra yayına alınsın.