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
