Longest Common Prefix
strs sözcüklerinden oluşan bir dizi veriliyor. Her sözcüğün başlangıcında bulunan en uzun dizgeyi döndürün. Sözcüklerin tümü aynı harfle başlamıyorsa boş dizgeyi "" döndürün. Bir sözcük kendisinin öneki sayılır; bu nedenle tek bir sözcük varsa yanıt sözcüğün kendisidir.
Fonksiyon
- 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 ≤ 2001 ≤ strs[i].length ≤ 200- Her kelime yalnızca küçük İngilizce harfler içerir.
Örnekler
- Girdi
- strs = ["interview", "internet", "interval", "internal"]
- Çıktı
- "inter"
- Açıklama
- Dört kelimenin de başında
intervardır. Bir sonraki konumdainterviewveintervalbirv,internetveinternalise birniçerir; bu nedenle ortak önek burada sona erer.
- Girdi
- strs = ["stack", "queue", "heap"]
- Çıktı
- ""
- Açıklama
- Kelimeler
s,qvehile başlıyor. İlk harfleri farklı olduğundan ortak bir önek yoktur ve yanıt boştur.
- Girdi
- strs = ["prefix", "pre", "prepare"]
- Çıktı
- "pre"
- Açıklama
preen kısa kelimedir ve diğer ikisi onunla başlar, bu yüzden cevabın tamamı odur. Ortak bir önek, en kısa kelimeden daha uzun olamaz.
Gönderirken +19 gizli test
Ek soru
Listenin sabit kaldığını ve çok sayıda sorgu sözcüğü aldığını varsayalım. Her seferinde listeyi yeniden taramadan, her sorgu için listedeki en az bir sözcükle paylaştığı en uzun öneki nasıl bulursun?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Yanıt hiçbir zaman en kısa sözcükten daha uzun olamaz. Yanıta ait her harf için ne doğru olmalıdır?
ikonumundaki bir harf, yalnızca her kelimeninikonumunda bir harfi varsa ve bu harflerin tümü aynıysa yanıta dahil olur. Yanıt, bu koşulun sağlanmadığı ilk konumda sona erer.İlk kelimenin konumlarında soldan sağa ilerleyin. Her konumda diğer tüm kelimeleri kontrol edin; içlerinden biri çok kısa olduğunda veya farklı bir harfe sahip olduğunda, ilk kelimenin o konumdan önceki kısmını döndürün.
Çözüm
Bir harf, yalnızca her kelimede aynı konumda aynı harf varsa yanıta dahildir ve yanıt, herhangi bir kelimenin farklı bir harfe sahip olduğu ya da tükendiği ilk konumda sona erer. Aşağıdaki iki yaklaşım da kelimeleri harf harf okur; okuma sıraları farklıdır. Sütunlara göre tarama ilk uyuşmazlıkta durur, bu yüzden yanıtın ötesinde en fazla bir sütun okur.
Öneki sözcük sözcük kısaltın
Sezgi
İlk sözcüğün tamamının yanıt olduğunu varsayarak başlayın. Ardından ikinci sözcükle harf harf karşılaştırın ve ortak olan kısma kadar kısaltın. Geriye kalanı üçüncü sözcükle karşılaştırın ve bu şekilde devam edin. Son sözcükten sonra geriye kalan, hepsinde ortak olandır.
Bu doğrudur; çünkü birçok sözcüğün ortak öneki, ilk iki sözcüğün ortak öneki, ardından bu sonucun üçüncü sözcükle ortak öneki ve bu şekilde devamıdır: her adımda yalnızca önek korunabilir ya da kısaltılabilir. interview, internet, interval, internal için aday, ikinci sözcükten 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 nedenle zaman karmaşıklığı O(S) olur; burada S, toplam harf sayısıdır. Yalnızca bir uzunluk tutarsınız, kopyasını değil. Zayıf nokta sıralamadır: ilk 199 sözcüğün uyuştuğu, yalnızca son sözcüğün ilk harfinde farklı olduğu 200 harfli 200 sözcükte, son sözcük öneki sıfıra indirmeden önce ilk 199 sözcüğün her biriyle 200 harfin tamamını karşılaştırırsınız; bu da yaklaşık 40.000 karşılaştırma demektir.
Algoritma
prefixLendeğerinistrs[0]uzunluğuna ayarla.- Diğer her kelime için,
prefixLendeğerine kadarstrs[0]ile paylaştığı baştaki harfleri say. prefixLendeğerini bu sayıya ayarla ve 0'a ulaşırsa işlemi erken durdur.strs[0]değerinin ilkprefixLenharfini 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 okuyun. 0. sütun her kelimenin ilk harfini, 1. sütun ikinci harfini ve böyle devamını içerir. Geçerli sütunda strs[0] içindeki harfi alın ve diğer tüm kelimelerin o sütunda aynı harfe sahip olup olmadığını kontrol edin. Bir kelimenin ilk kez farklı harfe sahip olduğu ya da o sütuna sahip olamayacak kadar kısa olduğu durumda yanıt, o sütuna kadar olan strs[0] değeridir.
Yanıt, tüm kelimelerin aynı harfe sahip olduğu sütunların tam olarak oluşturduğu dizidir ve bu döngü bu sütunları soldan başlayarak gezer, diziyi bozan ilk sütunda durur. Hiçbir sütun diziyi bozmazsa yanıt doğrudan strs[0] olur; bu durumda o, en kısa kelimedir ya da en kısa kelimeyle aynı uzunluktadır.
Döngü, yanıtın bir sütun ötesine kadar okur; bu nedenle n kelime ve L uzunluğunda bir yanıt için en fazla n × (L+1) kontrol yapar ve bir kelimenin aynı harfini asla iki kez okumaz; dolayısıyla karmaşıklığı yine O(S) olur. Yukarıdaki durumda, 199 kelimenin aynı olduğu ve son kelimenin ilk harfte farklılaştığı örnekte, ilk sütundan sonra durur: 40.000'e yakın karşılaştırma yerine 199 karşılaştırma yapar.
Algoritma
first,strs[0]olsun.- 0'dan
firstuzunluğunun bir eksiğine kadar hercolsütunu içinfirst[col]değerini oku. - Diğer her sözcük için,
colkonumunda bir harfi yoksa veya harfi farklıysa,first'in ilkcolharfini döndür. - Tüm sütunlar eşleşiyorsa
firstdeğ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
Yanıt kısadır ve hatalar sonunda ortaya çıkar.
- Daha kısa bir sözcüğün sonunu aşıp okumak.
prefix,pre,prepareörneğinde 3. sütunprefixiçinde vardır, ancakpreiçinde yoktur; harfi okumadan önce uzunluğu kontrol edin. - Verilen sıradaki yalnızca ilk ve son sözcüğü karşılaştırmak. Bu kestirme yöntem için önce sözcüklerin sıralanması gerekir:
abc,xbd,abdörneğinde ilk ve son sözcükabbölümünü paylaşır, ancakxbd0. sütunda eşleşmeyi bozar ve yanıt boştur. - Hiçbir şey ortak değilse
nullveya bir yer tutucu döndürmek. Yanıt boş dizedir. - Tek bir sözcüğün kendisinin öneki olduğunu unutmak: tek başına
algorithm,algorithmdöndürür. - Değişmez bir dizeye her seferinde bir harf ekleyerek yanıtı oluşturmak. 200 harflik bir yanıt için bu, 200 kopya oluşturur; uzunluğu takip edin ve en sonda ilk sözcüğü bir kez alın.
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, tüm sözcüklerdeki harflerin toplam sayısıdır ve yanıt dışında yalnızca O(1) ek bellek gerektirir. Sütun taraması ayrıca n × (L+1) ile sınırlıdır; bu nedenle sözcükler başlangıçta uyuşmadığında erken durur.
En uzun ortak öneki sözcükleri sıralayarak bulabilir misin?
Evet. Alfabetik sırada, ilk ve son kelime arasındaki her kelime, bu iki kelimenin ortak olarak başladığı harflerle başlar; dolayısıyla yalnızca ilk ve son kelimeyi karşılaştırmak yanıtı verir. Sıralama, yaklaşık n log n kelime ç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 "" döndürür. Bu, stack, queue ve heap sözcüklerinde olduğu gibi, iki sözcük farklı harflerle başlar başlamaz gerçekleşir.
Hangisi daha iyi, yatay mı dikey tarama mı?
Her ikisinin de en kötü durumu aynıdır: O(S). Dikey tarama, yani sütun sütun tarama, daha güvenli bir seçimdir: herhangi bir kelimenin uyuşmadığı ilk sütunda durur; yatay tarama ise sonlardaki bir kelime eşleşmeyi kesmeden önce uzun bir öneki birçok kelimeyle karşılaştırabilir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def longestCommonPrefix(strs):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
strs = ["interview", "internet", "interval", "internal"]
Beklenen
"inter"