Longest Common Prefix

Q: En Uzun Ortak Önek'in zaman karmaşıklığı nedir?

Her iki tarama da O(S) zamanda çalışır; burada S toplam harf sayısıdır ve yanıt dışında O(1) ek bellek kullanır. Sütun taraması ayrıca uzunluğu L olan bir yanıt için n × (L+1) ile sınırlıdır; bu nedenle sözcükler başlangıçta uyuşmadığında erken durur.

Q: Ortak bir önek olmadığında Longest Common Prefix ne döndürmelidir?

Boş dizge "" . İki sözcük farklı harflerle başlar başlamaz bu gerçekleşir; örneğin stack , queue ve heap .

Q: Hangisi daha iyidir, yatay tarama mı yoksa dikey tarama mı?

Her ikisinin de en kötü durum karmaşıklığı aynıdır: O(S) . Dikey tarama daha güvenli bir seçimdir: herhangi bir kelimenin uyuşmadığı ilk sütunda durur; yatay taramada ise sonlara doğru gelen bir kelime eşleşmeyi kesmeden önce uzun bir önek birçok kelimeyle karşılaştırılabilir.

KolayDiziler ve dizgiler

+10

Bir sözcük dizisi olan strs veriliyor. Her sözcüğün başlangıcında bulunan en uzun dizgeyi döndür. Sözcüklerin tümü aynı harfle başlamıyorsa boş dizgeyi "" döndür. Bir sözcük kendisinin öneki sayılır; bu nedenle tek bir sözcüğün yanıtı kendisidir.

Fonksiyon

longestCommonPrefix(strs: string-array) → string

strsstring-array: karşılaştırılacak sözcükler
Döndürürstring: tüm sözcüklerin paylaştığı en uzun önek veya boş bir dize

Kısıtlar

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Her sözcük yalnızca küçük İngilizce harfler içerir.

Örnekler

Girdi: strs = ["interview", "internet", "interval", "internal"]
Çıktı: "inter"
Açıklama: Dört kelimenin tümü inter ile başlar. Bir sonraki konumda interview ve interval bir v, internet ve internal ise bir n içerir; bu nedenle önek burada sona erer.

Girdi: strs = ["stack", "queue", "heap"]
Çıktı: ""
Açıklama: Kelimeler s, q ve h ile başlıyor. İlk harfleri aynı değil, bu yüzden yanıt boştur.

Girdi: strs = ["prefix", "pre", "prepare"]
Çıktı: "pre"
Açıklama: pre en kısa sözcüktür ve diğer iki sözcük onunla başlar; bu yüzden yanıtın tamamı budur. Ortak bir önek hiçbir zaman en kısa sözcükten daha uzun olamaz.

Ek soru

Listenin sabit kaldığını ve çok sayıda sorgu sözcüğü geldiğini varsayın. Listeyi yeniden taramadan, her sorgu sözcüğünün listedeki bir sözcükle paylaştığı en uzun öneki nasıl bulurdunuz?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir harf, yalnızca her kelimede aynı konumda bulunuyorsa yanıta dahildir ve yanıt, bir kelimenin farklılaştığı veya tükendiği ilk konumda sona erer. Her iki yaklaşım da kelimeleri harf harf, farklı bir sırayla okur. Sütunlara göre tarama, ilk farklılıkta durur.

Öneki kelime kelime kısaltın

Sezgi

İlk kelimenin tamamının yanıt olduğunu varsay. Onu önce ikinci kelimeyle, sonra üçüncüyle ve böyle devam ederek ortak olan kısmına indir. Birçok kelimenin ortak öneki, ilk iki kelimenin ortak önekiyle başlar; sonra bu önekin üçüncü kelimeyle ortak kısmı alınır: her adımda önek ya aynı kalır ya da kısalır. Örneğin 1'de aday, ikinci kelimeden sonra interview değerinden inter değerine iner ve orada kalır.

Her harf en fazla bir kez karşılaştırılır, bu yüzden tüm S harf için süre O(S) olur. Zayıf noktası sıralamadır: İlk harfi son kelimede farklı olan 200 harflik 200 kelime varsa, son kelime öneki sıfıra indirene kadar 40.000'e yakın karşılaştırma yaparsın.

Algoritma

prefixLen değerini strs[0] uzunluğuna ayarla.
Diğer her sözcük için, prefixLen değerini aşmayacak şekilde strs[0] ile paylaştığı baştaki harf sayısını say.
prefixLen değerini bu sayıya ayarla ve 0'a ulaşırsa işlemi erken durdur.
strs[0] değerinin ilk prefixLen harfini döndür.

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]

Sütun sütun karşılaştır

Sezgi

Kelimeleri bir tablo gibi, her seferinde bir sütun olacak şekilde oku. Geçerli sütundaki strs[0] harfini al ve diğer tüm kelimelerin o sütunda aynı harfe sahip olup olmadığını kontrol et. Bir kelimenin farklı olduğu ya da o sütuna kadar yeterince uzun olmadığı ilk durumda yanıt, strs[0] dizgesinin o sütuna kadar olan kısmıdır.

Yanıt, tüm kelimelerin aynı harfe sahip olduğu sütunların tam olarak ardışık dizisidir ve bu döngü, bu diziyi soldan başlayarak tarar ve dizinin bozulduğu yerde durur. Hiçbir şey diziyi bozmazsa yanıt strs[0] olur.

n kelime ve L uzunluğunda bir yanıt için döngü en fazla n × (L+1) kontrol yapar; bu aynı zamanda O(S) olur. 200 kelimeden yalnızca sonuncusu ilk harfinde farklıysa, 199 karşılaştırmadan sonra durur.

Algoritma

first değişkeni strs[0] olsun.
first uzunluğunun bir eksiğine kadar 0'dan başlayarak her col sütunu için first[col] değerini oku.
Diğer her sözcük için, col konumunda harf yoksa veya harfi farklıysa, first sözcüğünün ilk col harfini döndür.
Tüm sütunlar eşleşiyorsa first değerini döndür.

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

Tuzaklar ve uç durumlar

Daha kısa bir sözcüğün sonunu aşarak okumak. prefix, pre, prepare örneğinde, prefix içinde 3. sütun vardır ama pre içinde yoktur; harfi okumadan önce uzunluğu kontrol et.
Sıralama yapmadan yalnızca ilk ve son sözcüğü karşılaştırmak. abc, xbd, abd örneğinde ilk ve son sözcük ab ortak önekini paylaşır, ancak xbd 0. sütunu bozar ve yanıt boştur.
Ortak hiçbir şey yokken null veya bir yer tutucu döndürmek. Yanıt boş dizgedir.
Tek bir sözcüğün kendi öneki olduğunu unutmak: Tek başına algorithm, algorithm döndürür.
Değişmez bir dizgeye her seferinde bir harf eklemek. 200 harflik bir yanıt bu durumda 200 kopyalamaya mal olur; bir uzunluk tut ve ilk sözcüğü bir kez kes.

Sıkça sorulan sorular4

En Uzun Ortak Önek'in zaman karmaşıklığı nedir?

Her iki tarama da O(S) zamanda çalışır; burada S toplam harf sayısıdır ve yanıt dışında O(1) ek bellek kullanır. Sütun taraması ayrıca uzunluğu L olan bir yanıt için n × (L+1) ile sınırlıdır; bu nedenle sözcükler başlangıçta uyuşmadığında erken durur.

Sözcükleri sıralayarak en uzun ortak öneki bulabilir misin?

Evet. Alfabetik sırada, ilk ve son sözcük arasındaki her sözcük bu ikisinin ortak olarak başladığı harfle başlar; dolayısıyla yalnızca bu ikisini karşılaştırmak yanıtı verir. Sıralama, yaklaşık n log n sözcük çifti karşılaştırır; bu da tek bir taramadan daha maliyetlidir, ancak kod kısadır.

Ortak bir önek olmadığında Longest Common Prefix ne döndürmelidir?

Boş dizge "". İki sözcük farklı harflerle başlar başlamaz bu gerçekleşir; örneğin stack, queue ve heap.

Hangisi daha iyidir, yatay tarama mı yoksa dikey tarama mı?

Her ikisinin de en kötü durum karmaşıklığı aynıdır: O(S). Dikey tarama daha güvenli bir seçimdir: herhangi bir kelimenin uyuşmadığı ilk sütunda durur; yatay taramada ise sonlara doğru gelen bir kelime eşleşmeyi kesmeden önce uzun bir önek birçok kelimeyle karşılaştırılabilir.

def longestCommonPrefix(strs):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

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

Beklenen Çıktı

"inter"