Reverse Words in a String

Q: Berapa kompleksitas waktu untuk membalik urutan kata dalam string?

Kedua pendekatan berjalan dalam waktu O(n) untuk string dengan panjang n , karena setiap karakter dibaca dan ditulis sebanyak jumlah tetap. Pemisahan menggunakan ruang ekstra O(n) untuk list kata-kata. Membalik seluruh string lalu setiap kata membutuhkan ruang ekstra O(1) pada array karakter yang boleh kamu ubah.

SedangArray dan string Two pointers

+10

Kamu mendapatkan string s yang terdiri dari kata dan spasi. Kata adalah rangkaian huruf dan angka tanpa spasi di dalamnya. Kata dapat dipisahkan oleh lebih dari satu spasi, dan s dapat dimulai atau diakhiri dengan spasi.

Kembalikan kata-kata dalam urutan terbalik, gabungkan dengan tepat satu spasi, tanpa spasi di awal atau akhir. Ejaan setiap kata tetap sama, hanya urutan kata yang berubah.

Fungsi

reverseWords(s: string) → string

sstring: huruf, digit, dan spasi yang memuat setidaknya satu kata
Mengembalikanstring: kata-kata dari s dalam urutan terbalik, dipisahkan oleh spasi tunggal

Batasan

1 ≤ s.length ≤ 10⁴
s hanya berisi huruf, angka, dan spasi.
s berisi setidaknya satu kata.

Contoh

Input: s = "Coddy runs in 15 languages"
Output: "languages 15 in runs Coddy"
Penjelasan: Kata-katanya adalah Coddy, runs, in, 15 dan languages. Jika dibaca dari belakang ke depan, kata-kata itu membentuk languages 15 in runs Coddy; 15 dihitung sebagai sebuah kata karena kata dapat memuat digit.

Input: s = " practice makes progress "
Output: "progress makes practice"
Penjelasan: Spasi di kedua ujung dihilangkan, dan rangkaian dua dan tiga spasi di antara kata-kata diringkas menjadi satu spasi. Ketiga kata tersebut keluar dari yang terakhir hingga yang pertama: progress makes practice.

Input: s = " single "
Output: "single"
Penjelasan: Sebuah list yang terdiri dari satu kata tetap sama saat dibaca dari belakang. Hanya spasi di sekelilingnya yang dihilangkan, jadi jawabannya adalah single.

Pertanyaan lanjutan

Bisakah kamu membalik urutan kata tetapi mempertahankan spasi s: rentetan spasi yang sama, dengan panjang yang sama, dalam urutan yang sama?

Solusi

Urutan kata dibalik satu kali; spasi adalah bagian yang membuat solusi gagal. Spasi di kedua ujung dan spasi berulang di antara kata harus dihilangkan, sehingga ada tepat satu spasi di antara kata dalam jawaban. Kamu bisa memisahkan kata-kata menjadi sebuah list, atau membalik seluruh string lalu setiap kata di dalam satu array.

Pisahkan menjadi kata-kata lalu gabungkan dalam urutan terbalik

Intuisi

Pisahkan s menjadi kata-katanya, balik urutan list, lalu gabungkan dengan satu spasi. Proses pemisahan perlu dilakukan dengan hati-hati: memisahkan " practice makes progress " pada setiap spasi menghasilkan enam bagian kosong di sekitar tiga kata. Hapus bagian yang kosong, lalu list-nya menjadi practice, makes, progress.

Proses split membaca setiap karakter satu kali dan proses join menulis setiap karakter yang dipertahankan satu kali, jadi kompleksitas waktunya adalah O(n) untuk string dengan panjang n. List kata dan jawaban membutuhkan ruang ekstra O(n).

Algoritma

Pisahkan s berdasarkan spasi.
Buang bagian yang kosong.
Balik urutan list kata.
Gabungkan kata-kata dengan satu spasi di antara setiap kata, lalu kembalikan hasilnya.

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)

Balikkan seluruh string, lalu setiap kata

Intuisi

Membalik seluruh string menempatkan kata-kata dalam urutan yang benar, tetapi mengeja setiap kata secara terbalik: Coddy runs in 15 languages menjadi segaugnal 51 ni snur yddoC. Lalu, membalik setiap kata secara terpisah menghasilkan languages 15 in runs Coddy.

Spasi ditangani dalam lintasan yang sama. Indeks read menelusuri array yang telah dibalik dan melewati spasi; indeks write menandai tempat karakter berikutnya disimpan. Proses penyalinan tidak pernah menimpa karakter yang masih kamu perlukan, karena write tidak pernah melewati read: satu spasi yang ditulis sebelum sebuah kata menggantikan setidaknya satu spasi yang dilewati read.

Setiap karakter disalin paling banyak sekali dan ditukar paling banyak dua kali, jadi waktunya O(n), dengan ruang tambahan O(1) pada buffer karakter yang boleh kamu ubah. String di sini diterima sebagai nilai, jadi setiap solusi membuat satu salinan kerja dari s: total memori O(n).

Algoritma

Salin s ke dalam array karakter, lalu balik seluruh array.
Telusuri array dengan indeks baca dan lewati spasi.
Pada setiap kata, tulis satu spasi terlebih dahulu kecuali jika itu kata pertama, lalu salin karakter kata ke indeks tulis.
Balik bagian yang kamu salin agar kata terbaca dari depan.
Kembalikan write karakter pertama.

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])

Jebakan dan kasus tepi

Memisahkan berdasarkan satu spasi dan mempertahankan setiap bagian. "a b" terpisah menjadi a, bagian kosong, dan b, lalu penggabungan mengembalikan dua spasi: "b a".
Menganggap pemisahan akan menghapus bagian kosong di ujung. split(" ") Java menghapus bagian kosong di ujung, tetapi mempertahankannya di awal, jadi " a b" tetap menyisakan satu bagian kosong.
Menambahkan spasi setelah setiap kata, termasuk kata terakhir, sehingga jawaban berakhir dengan spasi. Letakkan spasi sebelum setiap kata kecuali kata pertama.
Hanya melakukan satu pembalikan pada versi yang mengubah data di tempat. Membalik kata-katanya saja menghasilkan yddoC snur ni 51 segaugnal.
Di PHP dan R, input yang hanya berisi angka seperti 2026 mungkin diterima sebagai angka. Ubah menjadi string sebelum memisahkannya.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk membalik urutan kata dalam string?

Kedua pendekatan berjalan dalam waktu O(n) untuk string dengan panjang n, karena setiap karakter dibaca dan ditulis sebanyak jumlah tetap. Pemisahan menggunakan ruang ekstra O(n) untuk list kata-kata. Membalik seluruh string lalu setiap kata membutuhkan ruang ekstra O(1) pada array karakter yang boleh kamu ubah.

Bagaimana cara menangani beberapa spasi di antara kata?

Anggap sebuah kata sebagai rangkaian karakter nonspasi dan jangan pernah menyalin spasi dari input. Pemisahan tanpa pemisah di Python dan Ruby, strings.Fields di Go, serta split_whitespace di Rust sudah melewati setiap rangkaian spasi dan spasi di kedua ujung; di tempat lain, buang bagian yang kosong. Lalu tulis satu spasi di antara kata-kata.

Bisakah kamu membalik urutan kata tanpa fungsi split?

Ya. Pindai dari ujung kanan: lewati spasi, tandai posisi akhir sebuah kata, bergerak ke kiri hingga awalnya, lalu tambahkan kata tersebut dengan spasi di depannya kecuali jika itu kata pertama. Setiap karakter dikunjungi satu kali, sehingga waktu tetap O(n), dan kata-katanya tersusun dalam urutan terbalik tanpa perlu membalik list.

def reverseWords(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "Coddy runs in 15 languages"

Output yang diharapkan

"languages 15 in runs Coddy"