Reverse Words in a String

Q: Bir Dizgedeki Kelimeleri Ters Çevirme işleminin zaman karmaşıklığı nedir?

Her iki yaklaşım da uzunluğu n olan bir dizge için O(n) zamanda çalışır; çünkü her karakter sabit sayıda okunup yazılır. Bölme işlemi, sözcük listesini tutmak için O(n) ek alan kullanır. Tüm dizgeyi ve ardından her sözcüğü ters çevirmek, düzenleyebileceğiniz bir karakter dizisi üzerinde O(1) ek alan gerektirir.

OrtaDiziler ve dizgiler İki işaretçi

+10

Harflerden ve boşluklardan oluşan bir s dizgesi veriliyor. Bir sözcük, içinde boşluk bulunmayan harf ve rakam dizisidir. Sözcükler birden fazla boşlukla ayrılabilir ve s boşlukla başlayabilir veya bitebilir.

Sözcükleri ters sırada, aralarında tam olarak bir boşluk olacak ve başında ya da sonunda boşluk olmayacak şekilde döndürün. Her sözcüğün yazımı aynı kalır; yalnızca sözcüklerin sırası değişir.

Fonksiyon

reverseWords(s: string) → string

sstring: En az bir kelime içeren harfler, rakamlar ve boşluklar
Döndürürstring: s'nin sözcükleri, ters sırada ve tek boşluklarla ayrılmış olarak

Kısıtlar

1 ≤ s.length ≤ 10⁴
s yalnızca İngilizce harfler, rakamlar ve boşluklar içerir.
s en az bir sözcük içerir.

Örnekler

Girdi: s = "Coddy runs in 15 languages"
Çıktı: "languages 15 in runs Coddy"
Açıklama: Kelimeler Coddy, runs, in, 15 ve languages. Son kelimeden ilkine doğru okunduğunda languages 15 in runs Coddy sonucunu verir; kelimeler rakam içerebildiğinden 15 bir kelime sayılır.

Girdi: s = " practice makes progress "
Çıktı: "progress makes practice"
Açıklama: Her iki uçtaki boşluklar silinir ve sözcüklerin arasındaki iki ve üç boşlukluk diziler tek boşluğa iner. Üç sözcük sondan başa doğru çıkar: progress makes practice.

Girdi: s = " single "
Çıktı: "single"
Açıklama: Tek kelimeden oluşan bir liste, tersten de aynı şekilde okunur. Yalnızca etrafındaki boşluklar kaldırılır, dolayısıyla yanıt single olur.

Ek soru

Kelimeleri tersine çevirip s'nin boşluk düzenini koruyabilir misin: aynı boşluk dizileri, aynı uzunluklarda ve aynı sırada?

Çözüm

Sözcüklerin sırası bir kez tersine çevrilir; çözümlerin bozulduğu yerler boşluklardır. Her iki uçtaki boşluklar ve sözcükler arasındaki yinelenen boşluklar kaldırılmalı, yanıtta sözcükler arasında tam olarak bir boşluk olmalıdır. Sözcükleri bir listeye ayırabilir ya da tüm dizgeyi, ardından tek bir dizinin içindeki her sözcüğü tersine çevirebilirsiniz.

Kelimelere ayır ve ters sırada birleştir

Sezgi

s dizgesini sözcüklerine ayır, listeyi tersine çevir ve aralarına tek boşluk koyarak birleştir. Ayırma işleminde dikkatli olmak gerekir: " practice makes progress " dizgesini her boşluk karakterinde ayırmak, üç sözcüğün çevresinde altı boş parça oluşturur. Boş parçaları atınca liste practice, makes, progress olur.

Ayırma işlemi her karakteri bir kez okur ve birleştirme işlemi tutulan her karakteri bir kez yazar; bu nedenle uzunluğu n olan bir dizge için zaman karmaşıklığı O(n) olur. Sözcük listesi ve sonuç O(n) ek alan kullanır.

Algoritma

s öğesini boşluklardan böl.
Boş parçaları at.
Sözcük listesini tersine çevir.
Sözcükleri aralarına birer boşluk koyarak birleştir ve sonucu döndür.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

Tüm dizgeyi, ardından her sözcüğü tersine çevirin

Sezgi

Tüm dizgeyi ters çevirmek sözcükleri doğru sıraya koyar ama her birini tersten yazar: Coddy runs in 15 languages, segaugnal 51 ni snur yddoC olur. Ardından her sözcüğü kendi içinde ters çevirmek languages 15 in runs Coddy sonucunu verir.

Boşluklar da aynı geçişte ele alınır. Bir read indeksi ters çevrilmiş dizide ilerler ve boşlukları atlar; bir write indeksi ise sıradaki korunacak karakterin nereye gideceğini belirtir. Kopyalama, hâlâ ihtiyaç duyduğun bir karakterin üzerine asla yazmaz; çünkü write hiçbir zaman read indeksini geçmez: bir sözcükten önce yazılan tek boşluk, read indeksinin atladığı en az bir boşluğun yerini tutar.

Her karakter en fazla bir kez kopyalanır ve en fazla iki kez yer değiştirir; bu nedenle zaman karmaşıklığı O(n), düzenleyebileceğin bir karakter tamponunda ek alan kullanımı ise O(1) olur. Burada dizgeler değer olarak gelir, bu yüzden her çözüm s değişkeninin bir çalışma kopyasını oluşturur: toplamda O(n) bellek.

Algoritma

s değişkenini bir karakter dizisine kopyala ve dizinin tamamını tersine çevir.
Bir okuma indeksiyle dizide ilerle ve boşlukları atla.
Her sözcükte, ilk sözcük değilse önce bir boşluk yaz; ardından sözcüğün karakterlerini yazma indeksine kopyala.
Sözcüğün düz okunması için kopyaladığın kısmı tersine çevir.
İlk write karakteri döndür.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

Tuzaklar ve uç durumlar

Tek bir boşlukla bölüp her parçayı korumak. "a b", a, boş bir parça ve b olarak bölünür; birleştirme iki boşluğu geri koyar: "b a".
Bölme işleminin baştaki ve sondaki boş parçaları attığını varsaymak. Java'da split(" ") sondaki boş parçaları atar ama baştakileri korur; bu yüzden " a b" hâlâ bir boş parça bırakır.
Sonuncusu da dahil olmak üzere her sözcükten sonra boşluk eklemek; böylece yanıt bir boşlukla biter. İlk sözcük dışındaki her sözcüğün önüne boşluk koy.
Yerinde sürümde yalnızca bir kez ters çevirme yapmak. Yalnızca sözcükleri ters çevirmek yddoC snur ni 51 segaugnal sonucunu verir.
PHP ve R'de 2026 gibi tamamen rakamlardan oluşan bir girdi sayı olarak gelebilir. Bölmeden önce onu bir dizgeye dönüştür.

Sıkça sorulan sorular3

Bir Dizgedeki Kelimeleri Ters Çevirme işleminin zaman karmaşıklığı nedir?

Her iki yaklaşım da uzunluğu n olan bir dizge için O(n) zamanda çalışır; çünkü her karakter sabit sayıda okunup yazılır. Bölme işlemi, sözcük listesini tutmak için O(n) ek alan kullanır. Tüm dizgeyi ve ardından her sözcüğü ters çevirmek, düzenleyebileceğiniz bir karakter dizisi üzerinde O(1) ek alan gerektirir.

Kelimeler arasındaki birden fazla boşluğu nasıl ele alırsın?

Bir sözcüğü, boşluk içermeyen karakterlerden oluşan bir dizi olarak ele al ve girdideki boşlukları asla kopyalama. Python ve Ruby'de ayırıcı belirtilmeden yapılan bir bölme, Go'daki strings.Fields ve Rust'taki split_whitespace zaten boşluk dizilerini ve her iki uçtaki boşlukları atlar; diğer dillerde boş parçaları çıkar. Ardından sözcüklerin arasına bir boşluk yaz.

split fonksiyonu kullanmadan kelimeleri ters çevirebilir misin?

Evet. Sağ uçtan tarayın: boşlukları atlayın, bir sözcüğün bittiği yeri işaretleyin, başlangıcına kadar sola ilerleyin ve ilk sözcük değilse önüne bir boşluk koyarak sözcüğü ekleyin. Her karakter bir kez ziyaret edilir; bu nedenle süre O(n) olarak kalır ve ters çevrilecek bir liste olmadan sözcükler ters sırada elde edilir.

def reverseWords(s):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

s = "Coddy runs in 15 languages"

Beklenen Çıktı

"languages 15 in runs Coddy"