Partition Labels

Q: Berapa kompleksitas waktu Partition Labels?

O(n) : satu kali lintasan mencatat posisi terakhir setiap huruf, lalu lintasan kedua menentukan letak pemotongan. Tabel posisi terakhir memiliki 26 entri untuk string dengan panjang berapa pun, jadi ruang tambahan adalah O(1) , tidak termasuk output.

SedangGreedy Hashing

+10

Kamu mendapatkan string s yang terdiri dari huruf kecil. Potong string ini menjadi sebanyak mungkin bagian berurutan sehingga setiap huruf hanya muncul di satu bagian: jika suatu huruf muncul di sebuah bagian, semua kemunculan huruf itu berada di bagian tersebut. Kembalikan panjang setiap bagian dari kiri ke kanan.

Fungsi

partitionLabels(s: string) → integer-array

sstring: string yang akan dipotong, hanya huruf kecil
Mengembalikaninteger-array: panjang setiap bagian, dari kiri ke kanan

Batasan

1 ≤ s.length ≤ 5 × 10⁴
s hanya berisi huruf kecil bahasa Inggris.
Bagian-bagian tersebut tetap berurutan dan secara bersama membentuk seluruh s, sehingga panjangnya jika dijumlahkan sama dengan s.length.

Contoh

Input: s = "abacdcefe"
Output: [3, 3, 3]
Penjelasan: Huruf a berada di posisi 0 dan 2, huruf c di posisi 3 dan 5, serta huruf e di posisi 6 dan 8. Jadi, pemotongan dilakukan setelah aba dan cdc, dan tidak ada bagian yang dapat dipotong lagi.

Petunjuk

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

0 dari 3 dibuka

Solusi

Pemotongan hanya boleh dilakukan jika tidak ada huruf yang muncul di kedua sisi, dan jawaban terbaik memotong di setiap tempat seperti itu. Memindai ulang string untuk setiap tempat membutuhkan waktu kuadratik. Catat posisi terakhir setiap huruf terlebih dahulu, lalu satu kali penelusuran dari kiri ke kanan akan menemukan setiap pemotongan: sebuah bagian harus membentang hingga kemunculan terakhir setiap huruf di dalamnya.

Uji setiap celah

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Potongan di salah satu dari n-1 celah boleh dibuat jika tidak ada huruf yang muncul di kedua sisinya. Membuat semua potongan yang boleh dibuat akan menghasilkan bagian terbanyak: di antara dua potongan berdekatan yang boleh dibuat, semua kemunculan setiap huruf berada di dalam bagian tersebut, sehingga bagian itu valid, dan tidak ada jawaban valid yang bisa membuat potongan di tempat lain.

Jadi, periksa setiap celah: kumpulkan huruf di setiap sisi, lalu buat potongan jika kedua himpunan tidak memiliki anggota yang sama. Dalam abacdcefe, celah setelah aba memiliki a dan b di sebelah kiri serta c, d, e, dan f di sebelah kanan, jadi kamu membuat potongan. Setiap pemeriksaan membaca seluruh string, sehingga jumlah pembacaan totalnya sekitar n²: 2.5 × 10^9 untuk n = 5 × 10^4.

Algoritma

Tetapkan start = 0, tempat bagian saat ini dimulai.
Untuk setiap celah cut dari 1 hingga n-1 (celah tepat sebelum s[cut]), tandai huruf-huruf pada s[0..cut-1] dan huruf-huruf pada s[cut..n-1].
Jika tidak ada huruf yang ditandai di kedua sisi, tambahkan cut-start ke jawaban dan tetapkan start = cut.
Setelah perulangan, tambahkan bagian terakhir, n-start.

def partitionLabels(s):
    n = len(s)
    sizes = []
    start = 0  # where the current part begins
    for cut in range(1, n):  # the gap just before s[cut]
        left = set(s[:cut])
        right = set(s[cut:])
        if not (left & right):  # no letter on both sides: cut here
            sizes.append(cut - start)
            start = cut
    sizes.append(n - start)  # the last part has no gap after it
    return sizes

Gabungkan rentang setiap huruf

Intuisi

Anggap setiap huruf sebagai interval dari posisi pertamanya hingga posisi terakhirnya. Bagian yang memuat sebuah huruf harus mencakup seluruh intervalnya, jadi interval yang bertumpang tindih berada di bagian yang sama, dan tumpang tindih itu menyebar: jika a bertumpang tindih dengan b dan b bertumpang tindih dengan c, ketiganya berada dalam satu bagian. Gabungkan interval yang bertumpang tindih; setiap blok hasil penggabungan adalah satu bagian.

Untuk menggabungkan interval, kamu memerlukan interval yang diurutkan berdasarkan posisi awalnya, dan kamu bisa mendapatkannya tanpa mengurutkan: telusuri string dan ambil interval sebuah huruf pada posisi pertamanya. Dalam codingisfun, i adalah [3, 6] dan n adalah [4, 10], dan g, s, f, serta u semuanya dimulai sebelum 10, jadi semuanya bergabung menjadi [3, 10]. Dengan paling banyak 26 huruf, tabel posisi memiliki ukuran tetap.

Algoritma

Dalam satu kali penelusuran s, catat first dan last, posisi pertama dan terakhir setiap huruf.
Telusuri s sekali lagi. Saat posisi i merupakan posisi pertama hurufnya, interval huruf itu, [i, last], menjadi interval berikutnya berdasarkan urutan awal.
Jika interval dimulai setelah end blok saat ini, tutup blok tersebut dengan panjang end-start+1, lalu mulai blok baru pada i.
Bagaimanapun, tetapkan end = max(end, last).
Tutup blok terakhir dan kembalikan panjangnya.

def partitionLabels(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        first.setdefault(c, i)
        last[c] = i
    sizes = []
    start = end = 0  # the block of merged spans being built
    for i, c in enumerate(s):
        if first[c] != i:
            continue  # take each letter's span once, at its first position
        if i > end:  # this span starts after the block: close the block
            sizes.append(end - start + 1)
            start = i
        end = max(end, last[c])
    sizes.append(end - start + 1)
    return sizes

Perbesar setiap bagian hingga mencapai huruf terakhirnya

Intuisi

Kamu tidak memerlukan posisi pertama. Baca dari kiri ke kanan dan simpan end, posisi terakhir paling jauh dari setiap huruf di bagian saat ini. Setiap huruf yang kamu baca memperpanjang end hingga salinan terakhirnya sendiri jika posisinya lebih jauh.

Saat i mencapai end, setiap huruf di bagian tersebut memiliki salinan terakhir pada posisi i atau sebelumnya, jadi celah setelah i diperbolehkan. Sebelum itu, beberapa huruf yang kamu baca masih memiliki salinan di sebelah kanan, jadi tidak ada celah lebih awal di bagian tersebut yang diperbolehkan. Proses ini memotong tepat di celah yang diperbolehkan. Dalam abacdcefe, a menetapkan end ke 2 dan bagian ditutup pada i = 2; c menetapkannya ke 5 dan bagian berikutnya ditutup pada 5.

Algoritma

Dalam satu kali pemindaian, simpan last[c], posisi terakhir setiap huruf c, dalam sebuah array berukuran 26.
Tetapkan start = 0 dan end = 0.
Untuk setiap posisi i, tetapkan end = max(end, last[s[i]]).
Jika i == end, tambahkan end-start+1 ke jawaban dan tetapkan start = i+1.
Kembalikan panjang-panjangnya.

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}  # last position of each letter
    sizes = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])  # the part must reach c's last copy
        if i == end:  # no letter of this part appears later
            sizes.append(end - start + 1)
            start = i + 1
    return sizes

Jebakan dan kasus tepi

Memotong pada kemunculan terakhir huruf saat ini, bukan pada end bagian tersebut. Dalam abcba, c pada indeks 2 adalah kemunculan terakhirnya, tetapi pemotongan di sana memisahkan a dan b.
Panjang yang selisih satu: bagian dari start hingga end, termasuk keduanya, memiliki end-start+1 huruf.
Mengembalikan posisi pemotongan, bukan panjangnya. Untuk abacdcefe, jawabannya adalah [3, 3, 3], bukan [2, 5, 8].
Lupa menambahkan bagian terakhir dalam versi celah. Tidak ada celah setelah bagian itu, jadi tambahkan n-start setelah perulangan.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Partition Labels?

O(n): satu kali lintasan mencatat posisi terakhir setiap huruf, lalu lintasan kedua menentukan letak pemotongan. Tabel posisi terakhir memiliki 26 entri untuk string dengan panjang berapa pun, jadi ruang tambahan adalah O(1), tidak termasuk output.

Apakah Partition Labels merupakan masalah penggabungan interval?

Ya. Setiap huruf mencakup rentang dari kemunculan pertamanya hingga kemunculan terakhirnya, lalu menggabungkan rentang yang tumpang tindih menghasilkan bagian-bagiannya. Proses greedy adalah penggabungan yang sama, dilakukan sambil berjalan, dengan end sebagai batas kanan blok yang sudah digabung sejauh ini.

Berapa banyak bagian yang dapat dikembalikan oleh Partition Labels?

Antara 1 dan 26. Setiap bagian memiliki setidaknya satu huruf yang tidak muncul di bagian lain, dan hanya ada 26 huruf kecil. String yang memuat setiap huruf tepat satu kali menghasilkan 26 bagian dengan panjang 1; string yang dimulai dan diakhiri dengan huruf yang sama menghasilkan satu bagian.

def partitionLabels(s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

s = "abacdcefe"

Output yang diharapkan

[3, 3, 3]

Partition Labels

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Uji setiap celah

Gabungkan rentang setiap huruf

Perbesar setiap bagian hingga mencapai huruf terakhirnya

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa