58. Length of Last Word LeetCode Problemi: Detaylı Analiz ve Çözüm Yaklaşımları

58. Length of Last Word LeetCode Problemi: Detaylı Analiz ve Çözüm Yaklaşımları

LeetCode’un “Top Interview 150” listesinde yer alan 58. problem olan “Length of Last Word”, size verilen bir string içindeki son kelimenin uzunluğunu bulmanızı isteyen temel ama önemli bir algoritma sorusudur. Bu problem, string manipülasyonu, köşe durumları (edge cases) ele alma ve verimli algoritma tasarlama becerilerinizi test etmek için harika bir fırsat sunar. Mülakatlarda sıkça karşılaşılan bu tür sorular, adayların sadece doğru cevabı bulmakla kalmayıp, aynı zamanda farklı yaklaşımları değerlendirebilme ve performans analizini yapabilme yeteneklerini de ölçer. Bu makalede, problemin detaylarına inecek, farklı çözüm stratejilerini inceleyecek, kod örnekleri sunacak ve performans analizleri yaparak en uygun yaklaşımları tartışacağız.

Problemin Tanımı ve Temel Gereksinimler

Herhangi bir algoritma problemine başlamadan önce, problemi tam olarak anlamak ve tüm gereksinimleri netleştirmek kritik öneme sahiptir. “Length of Last Word” problemi, basit görünen ancak dikkatli düşünmeyi gerektiren detaylara sahiptir.

Problemin Amacı

Size bir string (dize) s verilir. Göreviniz, bu string’deki son kelimenin uzunluğunu döndürmektir. Bir kelime, alfabetik karakterlerden oluşan ve boşluklarla ayrılmış bir karakter dizisi olarak tanımlanır. String’in sonunda veya arasında birden fazla boşluk olabilir.

Giriş ve Çıkış Formatı

• Giriş: Tek bir string s. Bu string, İngilizce büyük/küçük harflerden ve boşluk karakterlerinden oluşabilir.
• Çıkış: Bir tamsayı (integer), son kelimenin uzunluğu. Eğer string’de kelime yoksa (örneğin sadece boşluklardan oluşuyorsa), 0 döndürülmelidir.

Köşe Durumlar (Edge Cases)

Bu problemde göz önünde bulundurmanız gereken birkaç önemli köşe durum bulunmaktadır:

• Sondaki Boşluklar: “Hello World ” gibi bir string’de, sondaki boşlukların son kelimeyi (World) etkilememesi gerekir.
• Baştaki Boşluklar: ” Hello World” gibi bir string’de, baştaki boşluklar da göz ardı edilmelidir.
• Birden Fazla Boşluk: “Hello World” gibi bir string’de, kelimeler arasındaki birden fazla boşluğun doğru şekilde işlenmesi önemlidir.
• Sadece Boşluklardan Oluşan String: ” ” gibi bir string’de, sonuç 0 olmalıdır.
• Boş String: String boşsa, sonuç 0 olmalıdır.
• Tek Kelimelik String: “Word” veya ” Word ” gibi durumlarda, yine doğru uzunluk döndürülmelidir.

Neden Önemli? (Pratik Uygulamalar)

Bu problem, gerçek dünya uygulamalarında metin işleme, veri temizleme ve arama algoritmaları gibi alanlarda karşımıza çıkabilecek temel bir yapı taşıdır. Örneğin, bir kullanıcının girdiği metinden son anahtar kelimeyi çıkarmak, dosya yollarında son dizini veya dosya adını bulmak gibi senaryolarda bu mantık kullanılabilir. Ayrıca, string manipülasyonu becerilerini geliştirmek için harika bir alıştırmadır.

Temel Yaklaşım: String Metotları Kullanımı

Bu problemin en sezgisel ve çoğu programlama dilinde kolayca uygulanabilen çözümü, dilin sunduğu hazır string işleme metotlarını kullanmaktır. Bu yaklaşım genellikle kodun daha kısa ve okunabilir olmasını sağlar.

split() Metodu ile Çözüm

Çoğu modern programlama dili, bir string’i belirli bir ayırıcıya göre parçalara ayırarak bir dizi (liste) döndüren bir split() metoduna sahiptir. Boşluk karakteri (whitespace) bu ayırıcı olarak kullanılabilir.

strip() veya trim() Kullanımı

Problemin önemli bir detayı, string’in başında veya sonunda olabilecek boşluklardır. Bu boşluklar, son kelimeyi bulma işlemimizi yanıltabilir. Çoğu dilde, string’in başındaki ve sonundaki boşlukları kaldıran strip() (Python) veya trim() (Java/JavaScript) gibi metotlar bulunur. Bu metotları kullanarak string’i önceden temizlemek, işimizi oldukça kolaylaştırır.

Adım Adım Algoritma

1. Giriş string’inin başındaki ve sonundaki tüm boşlukları temizleyin (örneğin Python’da s.strip()).
2. Temizlenmiş string’i boşluk karakterine göre ayırarak kelimelerden oluşan bir liste elde edin (örneğin Python’da s.split(' ')).
3. Eğer kelime listesi boşsa (yani orijinal string sadece boşluklardan oluşuyorsa), 0 döndürün.
4. Listede eleman varsa, son elemanı (yani son kelimeyi) alın.
5. Son kelimenin uzunluğunu döndürün.

Kod Örneği (Python)

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        # 1. String'in başındaki ve sonundaki boşlukları temizle
        s_stripped = s.strip()

        # 2. Temizlenmiş string'i boşluklara göre ayırarak kelimeler listesi oluştur
        words = s_stripped.split(' ')

        # 3. Eğer kelime listesi boşsa (örneğin string sadece boşluklardan oluşuyorsa), 0 döndür
        if not words or (len(words) == 1 and not words[0]):
            return 0
        
        # 4. Son kelimeyi al ve uzunluğunu döndür
        # Not: split() metodu, birden fazla boşluğu tek bir ayırıcı olarak kabul eder
        # ve boş string'leri listeye eklemez, bu da işimizi kolaylaştırır.
        # Ancak, eğer split() boş string'leri de listeye ekleseydi (örn. 'a  b'.split(' ') -> ['a', '', 'b']),
        # o zaman boş string'leri filtrelememiz gerekebilirdi.
        # Python'ın varsayılan split() davranışı bu problem için uygundur.
        
        return len(words[-1])

# Test Durumları
# sol = Solution()
# print(sol.lengthOfLastWord("Hello World"))        # Çıkış: 5
# print(sol.lengthOfLastWord("   fly me   to   the moon  ")) # Çıkış: 4
# print(sol.lengthOfLastWord("luffy is still joyboy")) # Çıkış: 6
# print(sol.lengthOfLastWord("a"))                   # Çıkış: 1
# print(sol.lengthOfLastWord(" "))                   # Çıkış: 0
# print(sol.lengthOfLastWord("   a   "))            # Çıkış: 1

İki İşaretçi (Two-Pointer) Yaklaşımı

String metotları kullanmak kolay olsa da, bazı mülakatlarda string'i baştan sona kendiniz işlemeniz istenebilir veya performans kaygıları nedeniyle hazır metotlardan kaçınmanız gerekebilir. Bu durumda, iki işaretçi (two-pointer) tekniği oldukça verimli bir çözüm sunar.

Sağdan Sola Tarama Mantığı

Problemin "son kelime" ile ilgili olması, string'i sağdan sola doğru taramanın daha mantıklı olacağını gösterir. Bu sayede, ilk karşılaştığımız kelime doğrudan son kelime olacaktır ve baştaki boşluklarla uğraşmamıza gerek kalmaz.

Boşlukları Atlama ve Kelimeyi Sayma

Algoritma, string'in en sağından başlayarak karakterleri kontrol eder. İlk olarak, sondaki tüm boşlukları atlarız. Ardından, bir harf karakteriyle karşılaştığımızda, bu kelimenin başlangıcıdır. Bu noktadan itibaren sola doğru ilerlerken, kelimenin uzunluğunu saymaya başlarız. Bir boşlukla tekrar karşılaştığımızda veya string'in başına ulaştığımızda, kelime bitmiş demektir ve saydığımız uzunluk son kelimenin uzunluğudur.

Algoritma Detayları

1. Bir length değişkeni tanımlayın ve başlangıç değerini 0 yapın.
2. String'in en son karakterinden başlayarak (i = len(s) - 1) sola doğru ilerleyin.
3. İlk döngüde, sondaki tüm boşlukları atlayın: while i >= 0 and s[i] == ' ': i -= 1.
4. İkinci döngüde, bir harf karakteriyle karşılaştığınızda kelimenin uzunluğunu saymaya başlayın: while i >= 0 and s[i] != ' ': length += 1; i -= 1.
5. Kelime sayma döngüsü bittiğinde (yani bir boşlukla karşılaşıldığında veya string'in başına gelindiğinde), length değişkeni son kelimenin uzunluğunu tutacaktır. Bu değeri döndürün.

Kod Örneği (Python)

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        length = 0
        i = len(s) - 1

        # 1. Sondaki boşlukları atla
        while i >= 0 and s[i] == ' ':
            i -= 1

        # 2. Kelimenin uzunluğunu say
        while i >= 0 and s[i] != ' ':
            length += 1
            i -= 1
        
        return length

# Test Durumları
# sol = Solution()
# print(sol.lengthOfLastWord("Hello World"))        # Çıkış: 5
# print(sol.lengthOfLastWord("   fly me   to   the moon  ")) # Çıkış: 4
# print(sol.lengthOfLastWord("luffy is still joyboy")) # Çıkış: 6
# print(sol.lengthOfLastWord("a"))                   # Çıkış: 1
# print(sol.lengthOfLastWord(" "))                   # Çıkış: 0
# print(sol.lengthOfLastWord("   a   "))            # Çıkış: 1

Performans Analizi ve Karmaşıklık

Farklı çözüm yaklaşımlarının performansını anlamak, büyük veri kümeleriyle çalışırken veya kısıtlı kaynaklara sahip sistemlerde kritik öneme sahiptir. "Length of Last Word" problemi için iki ana yaklaşımın zaman ve alan karmaşıklıklarını inceleyelim.

Zaman Karmaşıklığı (Time Complexity)

• String Metotları Kullanımı (strip() ve split()):
  • strip() metodu, string'i baştan sona bir kez tarar. Bu O(N) zaman karmaşıklığına sahiptir, burada N string'in uzunluğudur.
  • split() metodu da string'i baştan sona bir kez tarar ve yeni bir liste oluşturur. Bu da O(N) zaman karmaşıklığına sahiptir.
  • Dolayısıyla, bu yaklaşımın toplam zaman karmaşıklığı O(N)'dir.
• İki İşaretçi (Two-Pointer) Yaklaşımı:
  • Bu yaklaşım, string'i en fazla bir kez (sağdan sola) tarar. En kötü durumda (tüm string tek bir kelimeyse veya sadece boşluklardan oluşuyorsa), tüm string'i taramak zorunda kalır.
  • Bu nedenle, iki işaretçi yaklaşımının zaman karmaşıklığı da O(N)'dir.

Her iki yaklaşım da lineer zaman karmaşıklığına sahiptir, yani string'in uzunluğu arttıkça çalışma süresi doğrusal olarak artar.

Alan Karmaşıklığı (Space Complexity)

• String Metotları Kullanımı (strip() ve split()):
  • strip() metodu genellikle orijinal string'in bir kopyasını döndürür, bu da O(N) alan gerektirebilir.
  • split() metodu, kelimeleri içeren yeni bir liste oluşturur. En kötü durumda (tüm string tek bir kelimeyse), bu liste yine O(N) alan kaplayabilir (string'in kendisi kadar). Eğer çok sayıda kısa kelime varsa, liste boyutu da N'e yakın olabilir.
  • Bu nedenle, bu yaklaşımın toplam alan karmaşıklığı O(N)'dir.
• İki İşaretçi (Two-Pointer) Yaklaşımı:
  • Bu yaklaşım, sadece birkaç değişken (length, i) kullanır ve yeni bir veri yapısı oluşturmaz.
  • Bu nedenle, iki işaretçi yaklaşımının alan karmaşıklığı O(1)'dir (sabit alan).

Yaklaşımların Karşılaştırılması

Aşağıdaki tablo, iki yaklaşımın performans özelliklerini özetlemektedir:

Optimizasyonlar

Alan karmaşıklığı açısından, iki işaretçi yaklaşımı daha optimize bir çözümdür çünkü sabit bellek kullanır. Zaman karmaşıklığı her iki durumda da O(N) olduğundan, bu problem için daha hızlı bir algoritma bulmak mümkün değildir, çünkü tüm string'i en az bir kez taramak zorundayız. Ancak, C++ gibi dillerde std::string::find_last_not_of ve std::string::find_last_of gibi metotlar, iki işaretçi yaklaşımının arkasındaki mantığı daha soyut bir şekilde sunarak kodun daha kısa olmasını sağlayabilir.

Farklı Programlama Dillerinde Uygulama

LeetCode problemleri genellikle birden fazla dilde çözülebilir. Yukarıda Python örneklerini gördük, şimdi Java ve C++'ta benzer yaklaşımları nasıl uygulayabileceğimize bakalım.

Java Örneği (String Metotları)

Java'da trim() ve split() metotları oldukça benzer şekilde çalışır. split() metodu regex (düzenli ifade) alabilir, bu da birden fazla boşluğu tek bir ayırıcı olarak ele almak için kullanışlıdır.

class Solution {
    public int lengthOfLastWord(String s) {
        String trimmedS = s.trim(); // Baştaki ve sondaki boşlukları kaldırır

        if (trimmedS.isEmpty()) { // Temizlenmiş string boşsa
            return 0;
        }

        // Boşluk karakterine göre ayırır. "\\s+" regex'i bir veya daha fazla boşluğu ifade eder.
        String[] words = trimmedS.split("\\s+");

        // Son kelimenin uzunluğunu döndür
        return words[words.length - 1].length();
    }
}

C++ Örneği (İki İşaretçi)

C++'ta string'ler üzerinde manuel olarak iterasyon yapmak Python'a göre biraz daha fazla kod gerektirebilir ancak mantık aynıdır. isspace() fonksiyonu bir karakterin boşluk olup olmadığını kontrol etmek için kullanılabilir.

#include 
#include  // isspace için

class Solution {
public:
    int lengthOfLastWord(std::string s) {
        int length = 0;
        int i = s.length() - 1;

        // Sondaki boşlukları atla
        while (i >= 0 && s[i] == ' ') { // std::isspace(s[i]) de kullanılabilir
            i--;
        }

        // Kelimenin uzunluğunu say
        while (i >= 0 && s[i] != ' ') { // std::isspace(s[i]) de kullanılabilir
            length++;
            i--;
        }
        
        return length;
    }
};

Dil Seçiminin Etkisi

Görüldüğü gibi, her dilde temel mantık aynı kalırken, sözdizimi ve bazı yardımcı fonksiyonlar farklılık gösterebilir. Python gibi diller string manipülasyonu için daha yüksek seviyeli ve özlü metotlar sunarken, C++ gibi diller daha düşük seviyeli kontrol imkanı verir. Mülakatlarda, genellikle en rahat olduğunuz dilde çözüm sunmanız beklenir, ancak farklı dillerdeki yaklaşımları bilmek, problem çözme yeteneğinizin genişliğini gösterir.

Yaygın Hatalar ve Dikkat Edilmesi Gerekenler

Bu problemde sıkça yapılan hatalar ve gözden kaçan detaylar bulunmaktadır. Bu noktalara dikkat etmek, doğru ve sağlam bir çözüm geliştirmenizi sağlar.

Sondaki Boşluklar

En yaygın hatalardan biri, string'in sonunda bulunan boşlukları göz ardı etmektir. "Hello World " gibi bir string'de, split() metodunu doğrudan kullanmak veya sağdan sola tarama yaparken boşlukları atlamamak yanlış sonuçlara yol açabilir. strip() kullanmak veya sağdan sola tararken ilk boşluk atlama döngüsünü doğru uygulamak bu sorunu çözer.

Sadece Boşluklardan Oluşan Dizeler

" " gibi sadece boşluklardan oluşan bir string verildiğinde, sonucun 0 olması beklenir. split() metodu kullanan çözümlerde, boş bir liste veya sadece boş string'lerden oluşan bir liste elde edilebilir. Bu durumu kontrol etmek ve 0 döndürmek önemlidir. İki işaretçi yaklaşımında ise, tüm string boşluklardan oluşuyorsa, i değişkeni -1'e düşecek ve length 0 kalacaktır, bu da doğal olarak doğru sonucu verir.

Boş Dize Durumu

Giriş string'i tamamen boşsa (""), sonucun 0 olması gerekir. strip() metodu boş string'i yine boş string olarak döndürür. split() metodu boş string üzerinde çağrıldığında bazı dillerde boş liste, bazılarında ise tek elemanlı (boş string içeren) bir liste döndürebilir. Bu durumların doğru şekilde ele alındığından emin olunmalıdır. İki işaretçi yaklaşımında, len(s) - 1 -1 olacağından döngüler çalışmaz ve length 0 olarak kalır.

Performans Tuzakları

Bazı dillerde string manipülasyonları beklenenden daha pahalı olabilir. Örneğin, Python'da string'ler immutable (değişmez) olduğu için, her strip() veya split() işlemi yeni bir string veya liste oluşturur. Bu, bellek kullanımı açısından önemlidir. Eğer performans kritikse ve string çok uzunsa, iki işaretçi gibi yerinde (in-place) işlem yapan algoritmalar tercih edilebilir.

Sonuç

"58. Length of Last Word" LeetCode problemi, basit görünse de string manipülasyonu, köşe durumları ele alma ve algoritma analizi gibi temel programlama becerilerini test eden değerli bir alıştırmadır. Bu makalede, problemi derinlemesine inceledik ve iki ana çözüm yaklaşımını detaylandırdık: dilin sunduğu string metotlarını kullanmak ve iki işaretçi tekniğiyle manuel olarak string'i taramak. Her iki yaklaşımın da zaman karmaşıklığı O(N) iken, iki işaretçi yaklaşımı O(1) sabit alan karmaşıklığı ile daha verimli bellek kullanımı sunar. Mülakatlarda, hem hızlı ve okunabilir bir çözüm sunabilmek hem de altında yatan mekanizmaları ve performans farklılıklarını açıklayabilmek önemlidir. Bu problem, temel algoritmik düşünme yeteneğinizi geliştirmeniz için harika bir başlangıç noktasıdır.

SSS (Sık Sorulan Sorular)

Neden bu problem sıkça sorulur?

Bu problem, string işleme, boşlukları yönetme, köşe durumları (boş string, sadece boşluklar, sondaki boşluklar) ele alma ve temel algoritma analizi (zaman/alan karmaşıklığı) gibi programlamanın temel taşlarını test ettiği için sıkça sorulur. Adayın problem anlama ve farklı yaklaşımları değerlendirme yeteneğini gösterir.

Hangi yaklaşım en iyisidir?

Genellikle "en iyi" yaklaşım, duruma ve kısıtlamalara bağlıdır. Eğer kodun okunabilirliği ve geliştirme hızı öncelikliyse ve bellek kullanımı çok kritik değilse, dilin hazır string metotlarını (strip() ve split()) kullanmak daha uygun olabilir. Ancak, bellek kullanımı kısıtlıysa veya daha düşük seviyeli kontrol isteniyorsa, iki işaretçi yaklaşımı (O(1) alan karmaşıklığı) tercih edilmelidir. Performans açısından her ikisi de O(N) zaman karmaşıklığına sahiptir.

Boş dize durumunda ne olmalı?

Giriş string'i boşsa ("") veya sadece boşluklardan oluşuyorsa (" "), problemin tanımına göre son kelimenin uzunluğu 0 olmalıdır. Çözümünüzün bu köşe durumu doğru şekilde ele aldığından emin olun.

String metotları kullanmak her zaman iyi bir fikir midir?

Hayır, her zaman iyi bir fikir değildir. String metotları genellikle daha az kodla daha fazla iş yapmanızı sağlasa da, bazı durumlarda performans veya bellek kullanımı açısından dezavantajlı olabilirler. Örneğin, çok uzun string'lerde split() metodu yeni bir string listesi oluşturarak önemli miktarda bellek tüketebilir. Ayrıca, bazı mülakatlarda, adayın string'i manuel olarak işlemesini ve dilin hazır metotlarına bağımlı olmamasını isteyen özel kısıtlamalar olabilir.