LeetCode 14: En Uzun Ortak Önek (Longest Common Prefix) Problemi Detaylı Analizi

LeetCode platformunda yer alan ve yazılım mülakatlarında sıkça karşılaşılan problemlerden biri olan “14. Longest Common Prefix” (En Uzun Ortak Önek) problemi, string manipülasyonu ve temel algoritma bilgisi gerektiren klasik bir sorudur. Bu makalede, bu problemin ne olduğunu, farklı çözüm yaklaşımlarını, bu yaklaşımların zaman ve uzay karmaşıklıklarını detaylı bir şekilde inceleyeceğiz. Amacımız, hem problemi derinlemesine anlamanızı sağlamak hem de mülakatlarda bu tür sorulara nasıl yaklaşmanız gerektiği konusunda size rehberlik etmektir.

Problemi Anlamak: “Longest Common Prefix” Nedir?

En Uzun Ortak Önek (Longest Common Prefix – LCP), verilen bir string dizisindeki tüm stringlerin ortak olarak sahip olduğu en uzun başlangıç kısmıdır. Eğer böyle bir ortak önek yoksa, boş bir string (“”) döndürülmelidir. Bu problem, veri işleme, dosya sistemleri, arama motorları ve hatta genetik dizilim analizleri gibi birçok gerçek dünya uygulamasında karşımıza çıkabilir.

Problem Tanımı

Size bir string dizisi strs verilecektir. Göreviniz, bu dizideki tüm stringlerin en uzun ortak öneki olan stringi bulmaktır. Eğer ortak bir önek bulunamazsa, boş bir string "" döndürün.

Örnekler ve Açıklamalar

Örnek 1:

Girdi: strs = ["flower","flow","flight"]
Çıktı: "fl"
Açıklama: “flower”, “flow” ve “flight” stringlerinin ortak başlangıç kısmı “fl”dir. “o” karakteri “flight” stringinde bulunmadığı için önek “flo” olamaz.

Örnek 2:

Girdi: strs = ["dog","racecar","car"]
Çıktı: ""
Açıklama: Verilen stringler arasında ortak bir önek bulunmamaktadır.

Örnek 3:

Girdi: strs = ["apple","apricot","apply"]
Çıktı: "ap"
Açıklama: Üç stringin de “ap” ile başladığı görülmektedir.

Neden Önemli?

Bu problem, string işleme yeteneklerinizi, döngüleri ve koşullu ifadeleri kullanma becerinizi ölçer. Mülakatlarda adayların problem çözme yaklaşımlarını, farklı algoritmaları karşılaştırma yeteneklerini ve kodlama pratiklerini değerlendirmek için ideal bir sorudur. Ayrıca, Trie (Prefix Tree) gibi gelişmiş veri yapılarına giriş için de iyi bir başlangıç noktası olabilir.

Çözüm Yaklaşımları: Genel Bakış

Longest Common Prefix problemini çözmek için birden fazla yol bulunmaktadır. Her bir yaklaşımın kendine göre avantajları ve dezavantajları vardır. Bu bölümde, en yaygın ve etkili yöntemlere genel bir bakış sunacağız.

Temel Algoritma Fikirleri

Problemi çözmek için genellikle üç ana kategoriye ayrılan yaklaşımlar mevcuttur:

Yatay Tarama (Horizontal Scanning): Öneki adım adım, her bir string ile karşılaştırarak kısaltma prensibine dayanır.
Dikey Tarama (Vertical Scanning): Her stringin aynı karakter indeksindeki elemanlarını karşılaştırarak öneki bulma prensibine dayanır.
Böl ve Yönet (Divide and Conquer): Problemi daha küçük alt problemlere bölerek özyinelemeli bir şekilde çözme prensibine dayanır.
Sıralama (Sorting): String dizisini alfabetik olarak sıralayarak ilk ve son stringin LCP’sini bulma prensibine dayanır.

Veri Yapısı Kullanımı (Trie)

Daha karmaşık senaryolarda veya çok sayıda LCP sorgusu gerektiğinde Trie (Prefix Tree) gibi özel veri yapıları da kullanılabilir. Ancak bu makalede daha çok temel algoritmik yaklaşımlara odaklanacağız.

Yatay Tarama (Horizontal Scanning) Yöntemi

Yatay tarama, LCP problemini çözmek için en sezgisel ve anlaşılması kolay yöntemlerden biridir. Bu yöntemde, ilk stringi başlangıç öneki olarak alırız ve bu öneki sırayla dizideki diğer tüm stringlerle karşılaştırırız. Eğer mevcut önek, bir sonraki stringin başlangıcı değilse, öneki bir karakter kısaltırız ve tekrar deneriz.

Yöntemin Açıklaması

Algoritma, ilk stringi potansiyel LCP olarak kabul eder. Daha sonra, bu potansiyel LCP’yi ikinci string ile karşılaştırır. Eğer ikinci string, potansiyel LCP ile başlamıyorsa, potansiyel LCP’nin son karakterini atar ve bu işlemi ikinci string ile tekrar dener. Bu işlem, potansiyel LCP, ikinci stringin bir öneki olana kadar devam eder. İkinci string ile ortak önek bulunduktan sonra, bu yeni (kısaltılmış) önek, üçüncü string ile aynı şekilde karşılaştırılır. Bu süreç, dizideki tüm stringler taranana kadar devam eder.

Algoritma Adımları

Eğer string dizisi boşsa, "" döndür.
İlk stringi prefix değişkenine ata.
İkinci stringden başlayarak dizideki her string (s) için:
1. s stringinin prefix ile başlayıp başlamadığını kontrol et. (s.startswith(prefix) veya s.find(prefix) == 0)
2. Eğer başlamıyorsa:
  1. prefix‘in son karakterini sil (prefix = prefix[:-1]).
  2. Eğer prefix boş bir string haline gelirse, bu, hiçbir ortak önek olmadığı anlamına gelir. Bu durumda "" döndür ve algoritmayı sonlandır.
  3. Adım 3.a’ya geri dön ve tekrar kontrol et.
Tüm stringler başarıyla kontrol edildikten sonra, en son kalan prefix değeri tüm stringlerin ortak öneki olacaktır. Bu değeri döndür.

Kod Örneği (Python)


def longestCommonPrefix_horizontal(strs):
    if not strs:
        return ""
    
    # İlk stringi başlangıç öneki olarak al
    prefix = strs[0]
    
    # İkinci stringden başlayarak tüm stringleri gez
    for i in range(1, len(strs)):
        # Mevcut prefix, strs[i]'nin öneki mi?
        # Değilse, prefix'i kısalt
        while strs[i].find(prefix) != 0:
            prefix = prefix[:-1] # Son karakteri sil
            if not prefix: # Eğer prefix boş string olursa, ortak önek yok demektir
                return ""
    
    return prefix

# Örnek kullanım:
print(longestCommonPrefix_horizontal(["flower","flow","flight"])) # Çıktı: fl
print(longestCommonPrefix_horizontal(["dog","racecar","car"]))   # Çıktı:
print(longestCommonPrefix_horizontal(["apple","apricot","apply"])) # Çıktı: ap

Avantajlar ve Dezavantajlar

Avantajlar:
- Anlaması ve uygulaması oldukça kolaydır.
- Sezgisel bir yaklaşımdır.
Dezavantajlar:
- find() veya startswith() gibi string metotlarının ve substring alma işlemlerinin maliyeti, özellikle Python gibi dillerde, her döngüde yeni string objeleri oluşturulmasına neden olabilir. Bu da performansı etkileyebilir.
- En kötü durumda, her string için birçok kısaltma işlemi gerekebilir.

Dikey Tarama (Vertical Scanning) Yöntemi

Dikey tarama yöntemi, yatay taramanın aksine, stringleri karakter karakter dikey olarak karşılaştırır. Bu yaklaşım, genellikle yatay taramadan daha verimli olabilir çünkü gereksiz substring kopyalama işlemlerinden kaçınır.

Yöntemin Açıklaması

Bu yöntemde, ilk stringin her karakterini sırayla ele alırız. Her karakter için, dizideki diğer tüm stringlerin aynı pozisyondaki karakterini kontrol ederiz. Eğer herhangi bir stringin o pozisyondaki karakteri, ilk stringin karakterinden farklıysa veya o stringin uzunluğu o pozisyona kadar gelmiyorsa (yani daha kısaysa), o noktaya kadar bulunan kısım en uzun ortak önektir. Bu durumda, ilk stringin o pozisyona kadar olan kısmını döndürürüz.

Algoritma Adımları

Eğer string dizisi boşsa, "" döndür.
İlk stringin karakterleri üzerinde bir dış döngü başlat (indeks j ile). Bu döngü, potansiyel LCP'nin uzunluğunu belirler.
Her j indeksi için:
1. İlk stringin j. karakterini (char = strs[0][j]) al.
2. İkinci stringden başlayarak dizideki diğer tüm stringler (strs[i]) üzerinde bir iç döngü başlat.
3. Her strs[i] stringi için:
  1. Eğer j, strs[i]'nin uzunluğuna eşitse (yani strs[i] daha kısaysa ve j indeksine kadar gelmiyorsa) VEYA strs[i][j] karakteri char'dan farklıysa:
    - Bu, ortak önekin j indeksinden önce bittiği anlamına gelir. İlk stringin 0'dan j'ye kadar olan kısmını (strs[0][:j]) döndür.
Eğer dış döngü tamamlanırsa (yani ilk stringin tüm karakterleri diğer tüm stringlerle eşleşirse), bu durumda ilk stringin tamamı ortak önektir. İlk stringi (strs[0]) döndür.

Kod Örneği (Python)


def longestCommonPrefix_vertical(strs):
    if not strs:
        return ""
    
    # İlk stringin karakterleri üzerinde döngü yap
    for j in range(len(strs[0])): # j, karakter indeksini temsil eder
        char = strs[0][j] # İlk stringin j. karakteri
        
        # Diğer stringleri gez
        for i in range(1, len(strs)): # i, string dizisindeki string indeksini temsil eder
            # Eğer mevcut string j indeksine kadar gelmiyorsa (daha kısaysa)
            # veya j. karakter ilk stringin j. karakteriyle eşleşmiyorsa
            if j == len(strs[i]) or strs[i][j] != char:
                # O zaman ortak önek 0'dan j'ye kadar olan kısımdır
                return strs[0][:j]
                
    # Eğer tüm karakterler eşleştiyse, ilk stringin tamamı ortaktır
    return strs[0]

# Örnek kullanım:
print(longestCommonPrefix_vertical(["flower","flow","flight"])) # Çıktı: fl
print(longestCommonPrefix_vertical(["dog","racecar","car"]))   # Çıktı:
print(longestCommonPrefix_vertical(["apple","apricot","apply"])) # Çıktı: ap

Avantajlar ve Dezavantajlar

Avantajlar:
- Genellikle yatay taramadan daha verimlidir çünkü string kopyalama veya alt string oluşturma maliyetlerinden kaçınır.
- Bellek kullanımı daha düşüktür (O(1) ek bellek).
Dezavantajlar:
- En kötü durumda (tüm stringler çok uzun bir ortak öneke sahipse), tüm stringleri neredeyse sonuna kadar taramak zorunda kalabilir.

Böl ve Yönet (Divide and Conquer) Yaklaşımı

Böl ve Yönet (Divide and Conquer), karmaşık bir problemi daha küçük, benzer alt problemlere bölerek ve bu alt problemlerin çözümlerini birleştirerek ana problemi çözme prensibine dayanan güçlü bir algoritma tasarım paradigmalarıdır. LCP problemine de bu yaklaşımla çözüm getirilebilir.

Yöntemin Açıklaması

Bu yöntemde, string dizisini özyinelemeli olarak ikiye böleriz. Her alt dizi için LCP'yi buluruz. Daha sonra, bu iki alt diziden elde edilen LCP'lerin ortak LCP'sini bularak ana problemin çözümüne ulaşırız. Bu süreç, alt dizide tek bir string kalana kadar devam eder.

Algoritma Adımları

Ana fonksiyon, string dizisini ve başlangıç/bitiş indekslerini alır.
Temel Durum: Eğer başlangıç indeksi bitiş indeksine eşitse (yani tek bir string varsa), o stringi döndür. Eğer başlangıç indeksi bitiş indeksinden büyükse (boş aralık), boş string döndür.
Bölme: Diziyi ortadan ikiye böl (mid = (sol + sag) // 2).
Yönetme (Özyinelemeli Çağrılar):
1. Sol yarı için LCP'yi özyinelemeli olarak bul (lcp_sol = divide_conquer_helper(strs, sol, mid)).
2. Sağ yarı için LCP'yi özyinelemeli olarak bul (lcp_sag = divide_conquer_helper(strs, mid + 1, sag)).
Birleştirme: lcp_sol ve lcp_sag stringlerinin en uzun ortak önekini bulan yardımcı bir fonksiyon (örneğin find_common_between_two(s1, s2)) kullanarak sonucu birleştir.

Yardımcı Fonksiyon: İki String Arasındaki LCP'yi Bulma

Bu yardımcı fonksiyon, iki stringi karakter karakter karşılaştırır ve ilk farklı karakteri bulduğu yere kadar olan kısmı döndürür.


def find_common_between_two(s1, s2):
    min_len = min(len(s1), len(s2))
    for i in range(min_len):
        if s1[i] != s2[i]:
            return s1[:i]
    return s1[:min_len] # Eğer bir fark bulunamazsa, daha kısa olan stringin tamamı ortaktır

Kod Örneği (Python)


def longestCommonPrefix_divide_conquer(strs):
    if not strs:
        return ""
    return divide_conquer_helper(strs, 0, len(strs) - 1)

def divide_conquer_helper(strs, left, right):
    if left == right: # Temel durum: tek bir string
        return strs[left]
    
    mid = (left + right) // 2
    lcp_left = divide_conquer_helper(strs, left, mid)         # Sol yarı için LCP'yi bul
    lcp_right = divide_conquer_helper(strs, mid + 1, right)    # Sağ yarı için LCP'yi bul
    
    return find_common_between_two(lcp_left, lcp_right) # İki LCP'nin ortak önekini bul

# Örnek kullanım:
print(longestCommonPrefix_divide_conquer(["flower","flow","flight"])) # Çıktı: fl
print(longestCommonPrefix_divide_conquer(["dog","racecar","car"]))   # Çıktı:
print(longestCommonPrefix_divide_conquer(["apple","apricot","apply"])) # Çıktı: ap

Avantajlar ve Dezavantajlar

Avantajlar:
- Problemi daha yönetilebilir alt parçalara böler.
- Paralel programlama ortamlarında potansiyel olarak daha verimli olabilir.
Dezavantajlar:
- Özyinelemeli çağrılar nedeniyle fonksiyon çağrı yığını (call stack) maliyeti vardır.
- Diğer yöntemlere göre daha karmaşık bir yapıya sahiptir.
- Pratikte, genellikle yatay veya dikey taramadan daha yavaş çalışabilir, özellikle string sayısı az ise.

Diğer Yaklaşımlar ve Veri Yapıları

LCP problemini çözmek için yukarıda bahsedilen temel yaklaşımların yanı sıra, bazı özel durumlarda veya farklı performans gereksinimleri olduğunda kullanılabilecek başka yöntemler de mevcuttur.

Sıralama (Sorting) Yaklaşımı

Bu yöntem oldukça zarif ve şaşırtıcı derecede etkilidir. Fikir şudur: Eğer bir string dizisini alfabetik olarak sıralarsak, en uzun ortak önek sadece dizinin ilk ve son stringi arasında bulunabilir. Çünkü ortak bir önek varsa, sıralama işlemi bu öneki koruyacaktır ve bu öneke sahip tüm stringler birbirine yakın konumlanacaktır. En uçtaki stringler (ilk ve son), ortak önekin en kısıtlayıcı sınırlarını belirleyecektir.

Algoritma Adımları

Eğer string dizisi boşsa, "" döndür.
String dizisini alfabetik olarak sırala.
Sıralanmış dizinin ilk stringini (first) ve son stringini (last) al.
first ve last stringlerini karakter karakter karşılaştır. İlk farklı karakteri bulduğun yere kadar olan kısım LCP'dir.
Bulunan LCP'yi döndür.

Kod Örneği (Python)


def longestCommonPrefix_sorting(strs):
    if not strs:
        return ""
    
    strs.sort() # String dizisini alfabetik olarak sırala
    
    first = strs[0]
    last = strs[-1]
    
    i = 0
    # İlk ve son stringin karakterlerini karşılaştır
    while i < len(first) and i < len(last) and first[i] == last[i]:
        i += 1
        
    return first[:i] # Ortak olan kısmı döndür

# Örnek kullanım:
print(longestCommonPrefix_sorting(["flower","flow","flight"])) # Çıktı: fl
print(longestCommonPrefix_sorting(["dog","racecar","car"]))   # Çıktı:
print(longestCommonPrefix_sorting(["apple","apricot","apply"])) # Çıktı: ap

Avantajlar ve Dezavantajlar

Avantajlar:
- Çözüm oldukça kısa ve okunabilir.
- Uygulaması kolaydır.

LeetCode 14: En Uzun Ortak Önek (Longest Common Prefix) Problemi Detaylı Analizi