Karakter Dizisinde Kelime Sırasını Etkili Bir Şekilde Tersine Çevirme

Karakter dizisinde kelime sırasını tersine çevirme, algoritmalar ve string manipülasyonu konusundaki bilginizi test eden klasik bir problemdir. Bir mülakata hazırlanıyorsanız veya sadece programlama becerilerinizi geliştirmek istiyorsanız, bu zorluğu başarmak oldukça tatmin edici olabilir. Bu yazıda, problemi detaylı bir şekilde inceleyecek ve C/C++ ile etkili bir çözümü parçalara ayıracağız.

Problem

Bir cümle oluşturan karakterlerden oluşan bir dizi verildiğinde, amacı kelimelerin sırasını tersine çevirmek ve kelimelerin içindeki bireysel harfleri değiştirmemektir. Örneğin, eğer girdi şöyle ise:

"this is a string"

Çıktı şöyle olmalıdır:

'string a is this'

Bu zorluk, işlemin O(N) zaman ve O(1) alan içinde gerçekleştirilmesi gerektiğini belirtmektedir, yani split() gibi fonksiyonlar veya ekstra alan kullanan yığın gibi veri yapıları kullanamazsınız.

Problemi Analiz Etme

Zaman Karmaşıklığı

O(N) zaman karmaşıklığı gereksinimi, algoritmanın veriler üzerinden lineer bir geçiş yapması gerektiği anlamına gelir. Bu nedenle, zaman karmaşıklığını artıran iç içe döngülerden kaçınmalıyız.

Alan Karmaşıklığı

O(1) alan karmaşıklığı için, depolama için ek veri yapıları kullanamayız. Bu, işlemlerin doğrudan giriş dizisi içinde gerçekleşmesi gerektiği anlamına gelir.

Çözüm

Çözümü adım adım inceleyelim. Bu problemi etkili bir şekilde çözmek için iki geçişli bir yaklaşım kullanacağız.

Adım 1: Tüm Diziyi Tersine Çevirme

İlk adım, tüm diziyi tersine çevirmektir. Bu, orijinal dizeyi tüm karakterlerin tersine çevrildiği bir dizeye dönüştürür. Örneğimiz olan "this is a string" tersine çevrildikten sonra:

"gnirts a si siht"

Adım 2: Her Kelimeyi Tersine Çevirme

Artık tüm dizeyi tersine çevirdiğimize göre, her bireysel kelimeyi doğru sıraya geri getirmek için tersine çevirmemiz gerekmektedir. Bu adımları C/C++ dilinde nasıl uygulayabileceğimizi gösterelim:

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // Tüm dizeyi tersine çevir
    reverse_string(str, strlen(str));
    int p = 0;
 
    // Kelime sınırlarını bul ve kelime kelime tersine çevir
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // Tanımlanan kelimeyi tersine çevir
            p = i + 1;
        }
    }
    // Son kelimeyi de tersine çevir.
    reverse_string(&str[p], l - p);
}

Kodun Açıklaması

1. Swap Fonksiyonu: Dizideki karakterleri değiştirmek için yardımcı bir swap fonksiyonu kullanıyoruz.
2. Diziyi Tersine Çevirme Fonksiyonu: Bu fonksiyon, karakterleri tersine çevirmek için swap fonksiyonunu kullanır.
3. Kelime Tersine Çevirme Fonksiyonu: Temel fonksiyon, önce tüm karakter dizisini tersine çevirir ve ardından boşluklarla belirlenen bireysel kelimeleri tersine çevirmek için üzerinde iterasyon yapar. Son kelime döngü sona erdikten sonra işlenir.

Karmaşıklık Analizi

Dizinin iki kez tersine çevrilmesi, zaman karmaşıklığını O(N) yapar:

• İlk geçiş: Tüm diziyi tersine çevirmek için O(N).
• İkinci geçiş: Her kelimeyi tersine çevirmek için O(N).

Böylece, son zaman karmaşıklığı O(N) olarak kalır. Alan karmaşıklığı O(1) olarak kalır çünkü döngü için kullanılan değişkenler dışında ek alan kullanılmaz.

Sonuç

Karakter dizisinde kelime sırasını etkili bir şekilde tersine çevirmek, string manipülasyonları ve dizin erişimi anlayışını gerektirir. Burada sunulan algoritma, C/C++ kullanarak O(N) zaman ve O(1) alan gereksinimlerini karşılayan net bir yaklaşım sergilemektedir. Bu çözümü pratik edin, programlama araç setinize mükemmel bir ekleme olduğunu göreceksiniz!