Longest Common Prefix

Q: Apa kompleksitas waktu dari Longest Common Prefix?

Kedua pemindaian berjalan dalam waktu O(S) , dengan S sebagai jumlah total huruf, dan menggunakan memori tambahan O(1) selain untuk jawaban. Pemindaian kolom juga dibatasi oleh n × (L+1) untuk jawaban dengan panjang L , sehingga berhenti lebih awal saat kata-katanya berbeda di dekat awal.

Q: Apa yang harus dikembalikan Longest Common Prefix jika tidak ada awalan yang sama?

String kosong "" . Itu terjadi begitu dua kata dimulai dengan huruf yang berbeda, seperti stack , queue , dan heap .

Q: Mana yang lebih baik, pemindaian horizontal atau vertikal?

Keduanya memiliki kasus terburuk yang sama, O(S) . Pemindaian vertikal adalah pilihan yang lebih aman: pemindaian ini berhenti pada kolom pertama saat ada kata yang tidak cocok, sedangkan pemindaian horizontal dapat membandingkan prefiks panjang dengan banyak kata sebelum kata yang muncul belakangan membatasinya.

MudahArray dan string

+10

Kamu mendapatkan sebuah array berisi kata-kata strs. Kembalikan string terpanjang yang menjadi awalan setiap kata. Jika tidak semua kata diawali dengan huruf yang sama, kembalikan string kosong "". Sebuah kata dianggap sebagai awalan dari dirinya sendiri, jadi jika hanya ada satu kata, kata itu menjadi jawabannya.

Fungsi

longestCommonPrefix(strs: string-array) → string

strsstring-array: kata-kata yang akan dibandingkan
Mengembalikanstring: prefiks terpanjang yang dimiliki semua kata, atau string kosong

Batasan

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Setiap kata hanya berisi huruf kecil bahasa Inggris.

Contoh

Input: strs = ["interview", "internet", "interval", "internal"]
Output: "inter"
Penjelasan: Keempat kata dimulai dengan inter. Pada posisi berikutnya, interview dan interval memiliki v, sedangkan internet dan internal memiliki n, jadi prefiks berhenti di sana.

Input: strs = ["stack", "queue", "heap"]
Output: ""
Penjelasan: Kata-kata tersebut diawali dengan s, q, dan h. Huruf pertama kata-kata tersebut berbeda, jadi jawabannya kosong.

Input: strs = ["prefix", "pre", "prepare"]
Output: "pre"
Penjelasan: pre adalah kata terpendek dan dua kata lainnya diawali dengannya, jadi itulah seluruh jawabannya. Prefiks yang sama tidak mungkin lebih panjang daripada kata terpendek.

Pertanyaan lanjutan

Misalkan list tetap dan banyak kata query berdatangan. Bagaimana kamu menemukan prefiks terpanjang dari setiap query yang sama dengan prefiks suatu kata dalam list, tanpa memindai ulang list?

Petunjuk

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

0 dari 3 dibuka

Solusi

Sebuah huruf termasuk dalam jawaban hanya jika setiap kata memilikinya di posisi yang sama, dan jawaban berakhir pada posisi pertama saat sebuah kata memiliki huruf yang berbeda atau kehabisan huruf. Kedua pendekatan membaca kata demi kata, huruf demi huruf, dengan urutan yang berbeda. Pemindaian berdasarkan kolom berhenti pada perbedaan pertama.

Shrink awalan kata demi kata

Intuisi

Anggap seluruh kata pertama sebagai jawabannya. Pangkas hingga hanya bagian yang sama dengan kata kedua, lalu dengan kata ketiga, dan seterusnya. Prefiks umum dari banyak kata adalah prefiks umum dari dua kata pertama, lalu dari prefiks itu dan kata ketiga: setiap langkah hanya dapat mempertahankan atau memperpendeknya. Misalnya, pada contoh 1, kandidat berubah dari interview menjadi inter setelah kata kedua dan tetap seperti itu.

Setiap huruf dibandingkan paling banyak satu kali, jadi waktunya O(S) untuk total S huruf. Kelemahannya adalah urutan: dengan 200 kata yang masing-masing terdiri dari 200 huruf, ketika hanya huruf pertama dari kata terakhir yang berbeda, kamu melakukan hampir 40.000 perbandingan sebelum kata terakhir memangkas prefiks hingga kosong.

Algoritma

Tetapkan prefixLen ke panjang strs[0].
Untuk setiap kata lainnya, hitung jumlah huruf awal yang sama dengan strs[0], hingga prefixLen.
Tetapkan prefixLen ke jumlah tersebut, lalu berhenti lebih awal jika nilainya mencapai 0.
Kembalikan prefixLen huruf pertama dari strs[0].

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

Bandingkan kolom demi kolom

Intuisi

Baca kata-kata seperti sebuah tabel, satu kolom setiap kali. Ambil huruf dari strs[0] pada kolom saat ini dan periksa apakah setiap kata lainnya memiliki huruf yang sama di sana. Saat pertama kali ada kata yang berbeda, atau terlalu pendek untuk memiliki huruf pada kolom itu, jawabannya adalah strs[0] hingga kolom tersebut.

Jawabannya tepat berupa rangkaian kolom yang hurufnya sama di semua kata, dan perulangan ini menelusuri rangkaian itu dari kiri lalu berhenti saat kesamaan itu terputus. Jika tidak ada yang memutuskannya, jawabannya adalah strs[0].

Dengan n kata dan jawaban sepanjang L, perulangan ini melakukan paling banyak n × (L+1) pemeriksaan, yang juga setara dengan O(S). Jika hanya kata terakhir dari 200 kata yang berbeda pada huruf pertamanya, proses berhenti setelah 199 perbandingan.

Algoritma

Tetapkan first sebagai strs[0].
Untuk setiap kolom col dari 0 hingga panjang first dikurangi satu, baca first[col].
Untuk setiap kata lainnya, jika tidak ada huruf pada col atau hurufnya berbeda, kembalikan col huruf pertama dari first.
Jika semua kolom cocok, kembalikan first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

Jebakan dan kasus tepi

Membaca melewati akhir kata yang lebih pendek. Dalam prefix, pre, prepare, kolom 3 ada di prefix, tetapi tidak ada di pre; periksa panjangnya sebelum membaca huruf tersebut.
Membandingkan hanya kata pertama dan terakhir tanpa mengurutkannya. Dalam abc, xbd, abd, kedua kata tersebut memiliki ab yang sama, tetapi xbd berbeda pada kolom 0 dan jawabannya adalah string kosong.
Mengembalikan null atau placeholder saat tidak ada yang sama. Jawabannya adalah string kosong.
Lupa bahwa satu kata merupakan prefix dari dirinya sendiri: algorithm saja menghasilkan algorithm.
Menambahkan satu huruf setiap kali ke string yang immutable. Jawaban 200 huruf akan membutuhkan 200 kali penyalinan; simpan panjangnya dan potong kata pertama sekali saja.

Pertanyaan yang sering diajukan4

Apa kompleksitas waktu dari Longest Common Prefix?

Kedua pemindaian berjalan dalam waktu O(S), dengan S sebagai jumlah total huruf, dan menggunakan memori tambahan O(1) selain untuk jawaban. Pemindaian kolom juga dibatasi oleh n × (L+1) untuk jawaban dengan panjang L, sehingga berhenti lebih awal saat kata-katanya berbeda di dekat awal.

Bisakah kamu menemukan prefiks umum terpanjang dengan mengurutkan kata-kata?

Ya. Dalam urutan alfabetis, setiap kata di antara kata pertama dan terakhir diawali dengan rangkaian huruf yang sama dengan kedua kata tersebut, jadi membandingkan kedua kata itu saja sudah memberikan jawabannya. Pengurutan membandingkan sekitar n log n pasangan kata, yang membutuhkan lebih banyak waktu daripada satu kali pemindaian, tetapi kodenya singkat.

Apa yang harus dikembalikan Longest Common Prefix jika tidak ada awalan yang sama?

String kosong "". Itu terjadi begitu dua kata dimulai dengan huruf yang berbeda, seperti stack, queue, dan heap.

Mana yang lebih baik, pemindaian horizontal atau vertikal?

Keduanya memiliki kasus terburuk yang sama, O(S). Pemindaian vertikal adalah pilihan yang lebih aman: pemindaian ini berhenti pada kolom pertama saat ada kata yang tidak cocok, sedangkan pemindaian horizontal dapat membandingkan prefiks panjang dengan banyak kata sebelum kata yang muncul belakangan membatasinya.

def longestCommonPrefix(strs):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

strs = ["interview", "internet", "interval", "internal"]

Output yang diharapkan

"inter"