Takip et

Bir String’deki Kelimeleri Ters Çevirme Algoritması

Bir String’deki Kelimeleri Ters Çevirme Algoritması

Bu makalede, LeetCode’da sıkça karşımıza çıkan 151. problem olan “Bir String’deki Kelimeleri Ters Çevirme” algoritmasını detaylı bir şekilde inceleyeceğiz. Öncelikle problemin tanımını yaparak, daha sonra farklı çözüm yöntemlerini ve bunların performans analizlerini ele alacağız. Son olarak da, en verimli çözümü belirleyip, kod örnekleri üzerinde tartışacağız. Umarım bu makale size bu algoritmayı anlamada yardımcı olur.

Problem Tanımı

Problem, verilen bir string’deki kelimelerin sırasını tersine çevirmeyi amaçlıyor. Örneğin, “the sky is blue” string’i “blue is sky the” şeklinde dönüştürülmelidir. Bu dönüşümde, her kelimenin içindeki harflerin sırası korunmalıdır. Ayrıca, fazladan boşluklar ve baştaki/sonundaki boşluklar da düzeltilmelidir. Bu problem, string manipülasyonu ve algoritmik düşünme becerilerinizi test etmek için idealdir.

Çözüm Yöntemleri

Bu problemi çözmek için birkaç farklı yaklaşım mevcuttur. İlk olarak, string’i kelime kelime ayırıp, bir diziye kaydedebilir, daha sonra bu diziyi tersine çevirebilir ve tekrar bir string’e birleştirebiliriz. Ancak bu yöntem, özellikle büyük string’ler için performans açısından verimsiz olabilir. Daha etkili bir yöntem, iki işaretçi kullanarak in-place ters çevirme işlemini gerçekleştirmektir. Bu yöntem, daha az bellek tüketimi ve daha iyi performans sunar.

Yöntem 1: Kelime Kelime Ayırma ve Ters Çevirme

Bu yöntemde, öncelikle string’i boşluklara göre ayırır, sonra oluşan kelimeleri bir diziye depolarız. Ardından bu diziyi tersine çevirir ve kelimeleri tekrar birleştirerek sonucu elde ederiz. Bu yöntem basit anlaşılır olsa da, ekstra bellek kullanımı sebebiyle performans açısından dezavantajlıdır.


def reverseWords1(s):
    words = s.split()
    return " ".join(words[::-1])

Yöntem 2: İki İşaretçi ile In-Place Ters Çevirme

Daha verimli olan ikinci yöntem, string’i üç aşamada ters çevirir: İlk olarak tüm string’i ters çevirir. Ardından her kelimeyi tek tek ters çevirir. Böylece, kelimeler doğru sırada, ama ters çevrilmiş bir şekilde olur. Sonuçta, verimli bir şekilde kelimelerin sırası ters çevrilmiş olur.


def reverseWords2(s):
    s = list(s)  # Stringi listeye çeviriyoruz
    # Tüm stringi ters çeviriyoruz
    reverse(s, 0, len(s) - 1)
    # Her kelimeyi ters çeviriyoruz
    start = 0
    for i in range(len(s)):
        if s[i] == ' ' or i == len(s) - 1:
            reverse(s, start, i - 1 if s[i] == ' ' else i)
            start = i + 1
    return "".join(s).strip()

def reverse(s, start, end):
    while start < end:
        s[start], s[end] = s[end], s[start]
        start += 1
        end -= 1

Performans Analizi

İlk yöntem, O(n) zaman karmaşıklığına ve O(n) ekstra alan karmaşıklığına sahiptir. İkinci yöntem ise, O(n) zaman karmaşıklığına ve O(1) ekstra alan karmaşıklığına sahiptir. Bu nedenle, ikinci yöntem, özellikle büyük string'ler için daha verimlidir. Bellek kullanımı açısından da ikinci yöntem daha avantajlıdır.

Sonuç

Bu makalede, bir string'deki kelimeleri ters çevirme problemini farklı yöntemlerle ele aldık. İkinci yöntemin, hem zaman hem de bellek açısından daha verimli olduğunu gördük. Bu yöntem, in-place işlemler sayesinde daha az kaynak tüketir ve büyük string'ler için tercih edilmelidir. Umarım bu makale size bu algoritmayı daha iyi anlamanıza yardımcı olmuştur. Daha fazla algoritma ve yazılım geliştirme içeriği için fatihsoysal.com sitesini ziyaret edebilirsiniz.

Faydalı Kaynaklar:

#Etiketler: Algoritma, String, Kelime Ters Çevirme, Python, Programlama, LeetCode, Veri Yapıları, Performans Analizi, Algoritma Analizi, Yazılım Geliştirme

Yorumlar
İçeriği beğendiniz mi? Bir tartışma başlatın veya görüşlerinizi paylaşın.
Yorum Yaz

Bir yanıt yazın

E-posta adresiniz yayınlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

E-posta Bülteni
Yazılım Topluluğuna Katılın
En son güncellemeleri, yaratıcı ipuçlarını ve özel kaynakları doğrudan e-posta kutunuza alın. Tasarım ve inovasyonun geleceğini birlikte keşfedelim.