Word Ladder
Sana iki kelime, beginWord ve endWord, ayrıca wordList adlı bir kelime listesi verilir. Merdiven, beginWord ile başlayan, endWord ile biten ve her kelimeden sonraki kelimeye geçerken tam olarak bir harfin değiştiği bir kelime dizisidir. beginWord sonrasındaki her kelime wordList içinden gelmelidir.
Her iki uç da sayılmak üzere en kısa merdivendeki kelime sayısını döndür; böyle bir merdiven yoksa 0 döndür. Örneğin, cold, cord, card 3 kelimelik bir merdivendir. beginWord'ün wordList içinde olması gerekmez, ancak endWord listede olmalıdır.
Fonksiyon
- beginWordstring
- merdivenin ilk kelimesi
- endWordstring
- Merdivenin ulaşması gereken kelime
- wordListstring-array
- Daha sonraki her adımın türemesi gereken kelimeler
- Döndürürinteger
- en kısa kelime zincirindeki kelime sayısı veya böyle bir zincir yoksa 0
Kısıtlar
1 ≤ beginWord.length ≤ 10endWordvewordListiçindeki her sözcük,beginWordile aynı uzunluğa sahiptir.1 ≤ wordList.length ≤ 5000- Tüm kelimeler yalnızca küçük İngilizce harflerden oluşur.
beginWord != endWord- The words in
wordListare all different.beginWordbunlardan biri olabilir de olmayabilir de.
Örnekler
- Girdi
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- Çıktı
- 4
- Açıklama
leadvegoldüç harfte farklıdır; bu nedenle hiçbir kelime merdiveni 4 kelimeden kısa olamaz velead,load,goad,goldtam olarak 4 kelimeden oluşur.lendvelewddaleadsözcüğünden tek harf farklıdır, ancak hiçbiri yeni bir yere götürmez veboldsözcüğüne yalnızcagoldsözcüğünden ulaşılabilir.
- Girdi
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- Çıktı
- 0
- Açıklama
cat,cot,cog,dog'a bir harf uzaklıktadır, ancakdoglistede olmadığı için hiçbir merdiven orada bitemez.
- Girdi
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- Çıktı
- 3
- Açıklama
ab,ad,cdveab,cb,cddizilerinin her ikisi de 3 kelime içerir.ablistede de yer alır, ancak başlangıç her iki durumda da bir kez sayılır.
Gönderirken +14 gizli test
Ek soru
En kısa merdivenlerden birini, yalnızca uzunluğunu değil, kelimeleri sırasıyla döndürebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her sözcüğü bir nokta olarak düşünün ve tam olarak bir harf farklı olan iki sözcüğün arasına bir çizgi çizin. Bu resimde bir merdiven nedir ve en kısa merdiven hangisidir?
En kısa merdiven, en az satır içeren yoldur ve her satır eşit ağırlıktadır. Genişlik öncelikli arama, iki adım uzaktaki herhangi bir sözcüğe ulaşmadan önce bir adım uzaktaki tüm sözcüklere ulaşır; bu nedenle
endWordsözcüğüne ilk ulaştığında en az adımı kullanmış olur. Bir sözcüğe ilk ulaştığın anda onu ziyaret edilmiş olarak işaretle.Komşularını bulmak için bir kelimeyi tüm listeyle karşılaştırmak yavaştır. Bunun yerine, her seferinde bir harfi gizle:
hot,hatvehitkelimelerinin tümüh*tolur. Her kelimeyi, kalıplarının her birine karşılık gelen kovaya koy. Bir kelimenin komşuları, kovalarındaki diğer kelimelerdir. AramayıbeginWordnoktasından başlayarak seviye seviye yürüt ve seviyeleri say.
Çözüm
Kelimeleri bir grafın düğümleri olarak ele al; tek bir harfleri farklı olan iki kelime arasında bir kenar olsun. Böylece merdiven, beginWord noktasından endWord noktasına giden bir yoldur ve her kenarın maliyeti aynıdır; dolayısıyla en kısa merdiven, en az kenar içeren yoldur. Genişlik öncelikli arama bunu tam olarak bulur. Problemi zorlaştıran, kenarları hızlı bulmaktır: 5.000 kelimenin her çiftini karşılaştırmak 25 milyon karşılaştırma demektir; bu yüzden en iyi çözüm, komşuları joker karakterli desenler üzerinden bulur. Aşağıda n kelime sayısını, L ise kelimelerin uzunluğunu belirtir.
Derinlik öncelikli aramayla her merdiveni dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
beginWord ile başla. Geçerli sözcükten, bir harf farkı olan ve henüz kullanılmamış her sözcüğü dene ve bu sözcükten daha derine in. endWord sözcüğüne ulaştığında, şu ana kadarki en kısa basamaklı diziyse uzunluğunu kaydet. Basamaklı dizinin kendi üzerine döngü yapmasını önlemek için geçerli yoldaki sözcükleri kullanılmış olarak işaretle ve diğer basamaklı dizilerin de kullanabilmesi için her sözcükten geri dönerken işaretini kaldır. best sözcükten oluşan bir basamaklı dizi bulduğunda, zaten best-1 sözcük içeren yolları uzatmayı bırak: bunlar daha kısa bir diziyle tamamlanamaz.
Bu yöntem doğrudur; çünkü bir sözcüğü asla tekrarlamayan tüm basamaklı dizileri dener ve en kısa basamaklı dizide de bir sözcük asla tekrarlanmaz: Bir sözcük iki kez geçiyorsa, bu iki kopya arasındaki kısmı çıkarmak daha kısa bir basamaklı dizi verir.
Yavaştır, çünkü basamaklı dizilerin sayısı hızla katlanır. İlk harfleri dışında aynı olan 26 sözcüğü ele alalım: aaa, baa ile zaa arasındaki sözcükler. Her çift bir harf farkı taşır; dolayısıyla arama, devam etmeden önce bunların arasında herhangi bir sırayla dolaşabilir ve 26 sözcük yaklaşık 4 × 10^26 farklı sırada dizilebilir. Budama ancak bir basamaklı dizi bulunduktan sonra işe yarar. endWord sözcüğüne hiçbir şekilde ulaşılamadığında hiçbir şey budanmaz ve 34 sözcüklük bir liste bile aramanın tamamlayabileceğinden fazladır. Özyineleme de basamaklı dizi kadar derine iner; bu dizi binlerce sözcük uzunluğunda olabilir.
Algoritma
beginWordlistedeyse kullanılmış olarak işaretleyin vebestdeğerini 0 olarak ayarlayın.search(word, length)yazın.word,endWordise,lengthdeğeribestdeğerinden daha iyi olduğundabestdeğerini güncelleyin ve döndürün.best0 değilse velength + 1 ≥ bestise döndürün: bu yol kazanamaz.wordsözcüğünden tek harf farkı olan kullanılmamış her sözcük için, onu kullanılmış olarak işaretleyin,search(next, length + 1)çağrısını yapın, ardından işaretini kaldırın.search(beginWord, 1)çağrısını yapın ve merdiven yoksa 0 olarak kalanbestdeğerini döndürün.
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
best = 0 # words in the shortest sequence found so far, 0 while there is none
used = [word == beginWord for word in wordList] # words on the current path
def search(word, length):
nonlocal best
if word == endWord:
if best == 0 or length < best:
best = length
return
if best != 0 and length + 1 >= best:
return # any longer path cannot beat the best one
for i, candidate in enumerate(wordList):
if not used[i] and one_letter_apart(word, candidate):
used[i] = True
search(candidate, length + 1)
used[i] = False # free the word for other paths
search(beginWord, 1)
return bestGenişlik öncelikli arama, her çifti karşılaştırma
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Genişlik öncelikli arama, sözcükleri uzaklık sırasına göre inceler. Önce beginWord, yani 1 sözcüklük bir basamak. Ardından ondan bir harf uzakta olan her sözcük, yani 2 basamak. Sonra bunlardan bir harf uzakta olan her yeni sözcük, yani 3 basamak ve böyle devam eder. Kuyruk bu sırayı korur: Sözcükler kuyruğa katıldıkları sırayla çıkar, bu nedenle d uzaklığındaki tüm sözcükler, d + 1 uzaklığındaki herhangi bir sözcükten önce çıkar.
BFS'nin bulduğu ilk basamağın neden en kısa basamak olduğunu bu sıra açıklar. Bir sözcüğe ilk kez d uzaklığında ulaşıldığında, d'den daha yakın olan tüm sözcükler zaten incelenmiştir; dolayısıyla o sözcüğe daha kısa bir basamak olsaydı, arama sözcüğe daha önce ulaşmış olurdu. Aynı mantık, bir sözcüğü kuyruğa katıldığı anda ziyaret edilmiş olarak işaretlemenin güvenli olmasını sağlar: Uzaklığı kesinleşmiştir ve ona daha sonra yeniden ulaşmak yalnızca daha uzun bir yol olabilir. Böylece her sözcük kuyruğa bir kez katılır ve endWord bir komşu olarak görünür görünmez uzaklığı yanıt olur.
Bu sürüm, bir sözcüğü listedeki her sözcükle harf harf karşılaştırarak ve ikinci farklılıkta durarak komşularını bulur. Kuyruktan çıkan en fazla n sözcüğün her biri, en fazla L harfi karşılaştırmak için n karşılaştırma gerektirir; dolayısıyla toplam karmaşıklık O(n² × L) olur. 5.000 sözcük ve bunların çoğunu ziyaret eden bir aramayla bu, 25 milyona kadar sözcük karşılaştırması demektir. Derlenen bir dil bunu hızla tamamlar, ancak Python en büyük testte birkaç saniyeye ihtiyaç duyar.
Algoritma
endWordwordListiçinde değilse 0 döndür.beginWorddeğerini uzunluğu 1 olan bir kuyruğa koy. Listede bulunuyorsa ziyaret edildi olarak işaretle.- Kuyruktan sıradaki kelimeyi ve uzunluğunu al.
- Bu kelimeyi listedeki ziyaret edilmemiş her kelimeyle karşılaştır. Aralarında tam olarak bir harf fark olan her kelime için:
endWordise uzunluk + 1 döndür; değilse ziyaret edildi olarak işaretle ve uzunluk + 1 ile kuyruğa ekle. - Kuyruk boşalırsa
endWorderişilemez durumdadır: 0 döndür.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
if endWord not in wordList:
return 0
visited = [word == beginWord for word in wordList]
queue = deque([(beginWord, 1)]) # (word, words in the sequence up to it)
while queue:
word, length = queue.popleft()
# Compare against every word to find the neighbours.
for i, candidate in enumerate(wordList):
if not visited[i] and one_letter_apart(word, candidate):
if candidate == endWord:
return length + 1
visited[i] = True
queue.append((candidate, length + 1))
return 0Joker karakter kovalarıyla genişlik öncelikli arama
Sezgi
Genişlik öncelikli aramayı koruyun ve komşuları bulmayı ucuz hâle getirin. İki kelime, her ikisinde de aynı konum gizlendiğinde eşit oluyorlarsa tam olarak bir harf farklıdır: hot ve hit ikisi de h*t olur. Bu yüzden her kelimeye gizlenen her konum için bir tane olmak üzere L desen verin ve kelimeyi her desen için bir kovaya ekleyin. Bir kelimenin komşuları, tüm listeyi taramak yerine L karma tablosu aramasıyla bulunan, L kovasındaki diğer kelimelerdir.
İlk örnekteki arama şöyledir. lead şu desenlere sahiptir: *ead, l*ad, le*d ve lea*. l*ad kovasında load, le*d kovasında ise lend ve lewd bulunur; dolayısıyla 2. seviyede bu üç kelime yer alır. load kelimesinden, *oad kovası 3. seviyede goad kelimesini verir; goad kelimesinden de go*d, 4. seviyede gold kelimesini verir.
Bir tasarruf daha: Bir kelimenin kovası tarandığında, içindeki tüm kelimelere ulaşılmış olur; bu yüzden kovayı boşaltın. Aynı deseni paylaşan sonraki kelimeler zaten orada yeni bir şey bulamaz. aaa, baa ve zaa'ya kadar olan kelimelerin *aa desenini paylaştığı testte, 26 kelimelik bu kova 26 kez değil, bir kez taranır. Böylece arama, n × L kova girdisinin her birini en fazla bir kez okur.
Desenleri oluşturmak, her biri L harften oluşan n × L dize gerektirir; zaman ve alan maliyeti O(n × L²) olur. Arama da aynı maliyete sahiptir: kuyruktan çıkan her kelime L desenini yeniden oluşturur. 10 harfli 5.000 kelime için bu, ikili karşılaştırmanın gerektirebileceği 250 milyona kadar harf adımına karşılık yaklaşık 500.000 harf adımıdır.
Algoritma
endWordwordListiçinde değilse 0 döndür.- Listedeki her sözcük ve
beginWordiçin, sözcüğüLdeseninin her birinin kovasına ekle. - Kuyruğu
beginWordile başlat, onu ziyaret edildi olarak işaretle ve uzunluğu 1 olarak ayarla. - Kuyruğu her seferinde bir düzey işle. Bir sözcük
endWordise uzunluğu döndür. Aksi takdirde, desenlerinin her biri için o kovadaki ziyaret edilmemiş tüm sözcükleri sonraki düzeye ekle, ziyaret edildi olarak işaretle ve kovayı boşalt. - Her düzeyden sonra uzunluğa 1 ekle. Kuyruk boşalırsa 0 döndür.
from collections import defaultdict, deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
size = len(beginWord)
# "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
buckets = defaultdict(list)
for word in set(wordList) | {beginWord}:
for i in range(size):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
visited = {beginWord}
queue = deque([beginWord])
length = 1 # words in the sequence up to the current level
while queue:
for _ in range(len(queue)): # one level: every word at this distance
word = queue.popleft()
if word == endWord:
return length
for i in range(size):
pattern = word[:i] + "*" + word[i + 1:]
for neighbour in buckets[pattern]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
buckets[pattern] = [] # all of them are visited now: never scan it again
length += 1
return 0
Tuzaklar ve uç durumlar
Çoğu yanlış yanıt, yanlış şeyi saymaktan veya endWord ile ilgili kuralı gözden kaçırmaktan kaynaklanır.
- Değişiklik sayısı yerine kelime sayısını döndürmek.
leadsözcüğündengoldsözcüğüne dönüşüm 3 değişiklik ve 4 kelime alır; yanıt 4'tür. endWordsözcüğününwordListiçinde olup olmadığını kontrol etmemek. İkinci örnekte arama,dogsözcüğünden bir harf alır, ancak yanıt 0'dır.- Derinlik öncelikli arama kullanıp bulduğu ilk dönüşüm zincirini döndürmek. DFS bir dalı sonuna kadar izler, bu nedenle bulduğu ilk zincir genellikle uzundur.
- Bir sözcüğü kuyruğa eklendiğinde değil, kuyruktan çıkarıldığında ziyaret edildi olarak işaretlemek. Böylece 26 sözcüklü dolu bir kovadaki bir sözcük kuyruğa 25 defaya kadar eklenebilir ve kuyruk
ndeğerini çok aşacak kadar büyür. beginWordaynı zamandawordListiçindeyse onu işaretlememek. Arama iki seviye sonra ona yeniden ulaşır ve aynı işi tekrarlar. Başlangıçtan itibaren ziyaret edildi olarak işaretle.- En fazla bir harfi farklı olan sözcükleri aramak. Her sözcük kendisinden sıfır harfte farklıdır; bu nedenle koşul tam olarak bir harf farklı olmasıdır.
- Dönüşüm zinciri boyunca özyinelemeli çağrı yapmak. Gizli bir testte en kısa dönüşüm zinciri 1.500 sözcük uzunluğundadır; bu, bazı dillerde çağrı yığınının taşmasına yetecek kadar derindir. BFS için yalnızca bir kuyruk gerekir.
Sıkça sorulan sorular4
Genişlik öncelikli arama neden en kısa kelime zincirini bulur?
BFS, sözcükleri turlar hâlinde inceler: önce başlangıç sözcüğünü, sonra tek değişiklik uzaklıktaki her sözcüğü, ardından iki değişiklik uzaklıktaki her sözcüğü. Bir sözcüğe, ona ulaşabilen en erken turda ilk kez ulaşılır; bu nedenle uzaklığı, mümkün olan en az değişiklik sayısıdır. Bu yalnızca her değişikliğin aynı maliyete sahip olması sayesinde işe yarar. Adım başına maliyetler farklı olsaydı bunun yerine Dijkstra algoritmasına ihtiyaç duyardınız.
Word Ladder'ın zaman karmaşıklığı nedir?
Joker karakter kovalarıyla, desenleri oluşturmak ve aramayı çalıştırmak, L uzunluğundaki n sözcük için O(n × L²) zaman alır; çünkü her sözcüğün L harften oluşan L deseni vardır. Her sözcük çiftini karşılaştırmak bunun yerine O(n² × L) maliyetlidir ve derinlik öncelikli aramayla her merdiveni denemek üstel zaman alır.
Bir harf farkı olan kelimeleri nasıl bulursunuz?
Bir yol, yukarıdaki joker karakter kovalarıdır: h*t gibi bir deseni paylaşan kelimeler komşudur. Diğer yol ise kelimenin her konumunu 26 harfin her biriyle değiştirmek ve sonucu kelimelerden oluşan bir hash kümesinde aramaktır. Bu, kelime başına 26 × L arama gerektirir ve her aramada L harf hash'lenir; dolayısıyla toplamda O(n × 26 × L²) olur. Her iki yöntem de tüm listeyle karşılaştırmaktan daha iyidir.
Çift yönlü BFS, Word Ladder'ı hızlandırabilir mi?
Evet. beginWord ve endWord sözcüklerinden aynı anda arama yap, her zaman küçük olan tarafı bir seviye büyüt ve yeni bir sözcüğe diğer taraf zaten ulaşmışsa dur. Merdivende, her iki tarafta yapılan değişikliklerin toplamından bir sözcük daha fazla bulunur. Her sözcüğün yaklaşık b komşusu varsa ve merdiven d değişiklik gerektiriyorsa, tek bir arama yaklaşık b^d sözcüğe dokunabilir; ortada buluşan iki arama ise yaklaşık 2 × b^(d/2) sözcüğe dokunur.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def ladderLength(beginWord, endWord, wordList):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Beklenen
4