Reverse a String

Q: Berapa kompleksitas waktu untuk membalik string?

Membalik string memerlukan waktu O(n) , karena setiap karakter harus berpindah ke posisi baru dan diproses satu kali. Membuat string baru memerlukan ruang tambahan sebesar O(n) . Menukar karakter dengan dua pointer hanya memerlukan ruang tambahan sebesar O(1) jika karakter sudah berada dalam array yang bisa diubah.

Q: Bagaimana cara membalik string tanpa fungsi reverse bawaan?

Salin karakter ke dalam array, tempatkan satu pointer di setiap ujung, tukar kedua karakter, lalu gerakkan pointer saling mendekat hingga bertemu. Sebagai alternatif, lakukan perulangan dari indeks terakhir ke indeks pertama dan tambahkan setiap karakter ke builder. Keduanya menghasilkan string terbalik dalam satu kali lintasan.

Q: Bisakah kamu membalik string secara langsung?

Hanya jika karakter berada dalam buffer yang dapat diubah, seperti array char di C, Java, atau C#, list di Python, atau std::string di C++. string di Java, Python, dan JavaScript tidak dapat diubah, jadi salin string tersebut ke dalam array, tukar karakter di sana, lalu buat string baru.

PemulaArray dan string Two pointers

+10

Kamu mendapatkan string s yang terdiri dari huruf dan angka. Kembalikan string baru dengan karakter yang sama dalam urutan terbalik, sehingga karakter terakhir berada di awal dan karakter pertama berada di akhir. Pertahankan setiap karakter persis seperti semula, termasuk huruf besar atau kecilnya.

Fungsi

reverseString(s: string) → string

sstring: string yang akan dibalik
Mengembalikanstring: karakter-karakter s dalam urutan terbalik

Batasan

1 ≤ s.length ≤ 10⁴
s hanya berisi huruf Inggris (a sampai z, A sampai Z) dan digit (0 sampai 9).

Contoh

Input: s = "Coddy2026"
Output: "6202yddoC"
Penjelasan: Baca Coddy2026 dari karakter terakhir hingga karakter pertama: 6, 2, 0, 2, lalu y, d, d, o, dan terakhir huruf kapital C.

Input: s = "noon"
Output: "noon"
Penjelasan: noon adalah palindrom, jadi kebalikannya adalah kata yang sama. Huruf n di bagian luar bertukar tempat, lalu kedua huruf o juga.

Pertanyaan lanjutan

Bagaimana cara membalik urutan kata dalam sebuah kalimat, mengubah hello big world menjadi world big hello, sementara setiap kata tetap mempertahankan urutan hurufnya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap karakter memiliki tujuan tetap: karakter pada indeks i harus berada pada indeks n-1-i. Kamu bisa menulis karakter ke dalam string baru dengan urutan tersebut, atau menukarnya secara berpasangan dari kedua ujung. Versi dengan pertukaran adalah yang biasa ditanyakan pewawancara, karena pergerakan dua pointer yang sama membalik array langsung di tempat dan memeriksa palindrom.

Salin karakter dari bagian belakang

Intuisi

Pembalikan dimulai dari karakter terakhir dan berakhir pada karakter pertama, jadi lakukan perulangan dengan indeks dari n-1 turun hingga 0, lalu tambahkan setiap karakter ke jawaban. Setiap karakter dibaca sekali dan ditulis sekali: waktu O(n), ditambah string jawaban berukuran O(n).

Tambahkan karakter ke list atau string builder, lalu gabungkan sekali di akhir. Menambahkan satu karakter ke string immutable dengan + menyalin seluruh string setiap kali, sekitar 5 × 10^7 penyalinan karakter untuk n = 10^4.

Algoritma

Buat list kosong atau string builder untuk jawabannya.
Lakukan perulangan i dari n-1 turun hingga 0.
Tambahkan s[i] ke jawaban.
Gabungkan jawaban menjadi string, lalu kembalikan.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

Tukar dari kedua ujung dengan dua pointer

Intuisi

Karakter pertama dan terakhir bertukar tempat, lalu karakter kedua dan kedua dari belakang, dan seterusnya menuju tengah. Letakkan left pada indeks 0 dan right pada n-1, tukar, lalu geser keduanya ke arah tengah sampai bertemu atau berpapasan. Setiap pertukaran menempatkan dua karakter di posisi akhirnya, jadi n / 2 pertukaran sudah cukup. Untuk panjang ganjil seperti xYz, karakter tengah sudah berada di posisinya dan tidak pernah disentuh.

Pertukaran ini membutuhkan satu variabel sementara. Sebagian besar bahasa tidak dapat mengubah string secara langsung, jadi kamu harus menyalinnya terlebih dahulu ke dalam array karakter, yang membutuhkan O(n). Jika input sudah berupa array yang dapat diubah, pembalikan menggunakan ruang tambahan O(1).

Algoritma

Salin s ke dalam array karakter.
Tetapkan left = 0 dan right = n-1.
Selama left < right, tukar karakter pada left dan right, lalu tambahkan 1 ke left dan kurangi 1 dari right.
Ubah array kembali menjadi string dan kembalikan.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Jebakan dan kasus tepi

Melakukan perulangan pada left sampai ke n-1. Setelah melewati bagian tengah, setiap pasangan ditukar kembali, sehingga string kembali tanpa perubahan. Berhenti saat left < right.
Memulai perulangan mundur dari n, bukan n-1, sehingga membaca satu posisi melewati akhir. Di Lua dan R, indeks dimulai dari 1 hingga n.
Lupa menambahkan '\0' sebagai terminator di C. Buffer berukuran n byte kurang satu, alokasikan n + 1.
Menukar tanpa variabel sementara. Setelah chars[left] = chars[right], karakter lama di posisi kiri hilang, kecuali bahasa yang kamu gunakan menukar kedua nilai sekaligus.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk membalik string?

Membalik string memerlukan waktu O(n), karena setiap karakter harus berpindah ke posisi baru dan diproses satu kali. Membuat string baru memerlukan ruang tambahan sebesar O(n). Menukar karakter dengan dua pointer hanya memerlukan ruang tambahan sebesar O(1) jika karakter sudah berada dalam array yang bisa diubah.

Bagaimana cara membalik string tanpa fungsi reverse bawaan?

Salin karakter ke dalam array, tempatkan satu pointer di setiap ujung, tukar kedua karakter, lalu gerakkan pointer saling mendekat hingga bertemu. Sebagai alternatif, lakukan perulangan dari indeks terakhir ke indeks pertama dan tambahkan setiap karakter ke builder. Keduanya menghasilkan string terbalik dalam satu kali lintasan.

Bisakah kamu membalik string secara langsung?

Hanya jika karakter berada dalam buffer yang dapat diubah, seperti array char di C, Java, atau C#, list di Python, atau std::string di C++. string di Java, Python, dan JavaScript tidak dapat diubah, jadi salin string tersebut ke dalam array, tukar karakter di sana, lalu buat string baru.

def reverseString(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "Coddy2026"

Output yang diharapkan

"6202yddoC"