Alien Dictionary

+10

Bir kelime listesi, bilmediğiniz bir alfabeye göre sıralanmıştır: 26 küçük İngilizce harf, gizli bir sıraya göre dizilmiştir. Kelimeler alışılmış şekilde karşılaştırılır. İki kelimenin farklı olduğu ilk konumda, alfabede hangi harfin önce geldiğine bakılır; bir kelime diğerinin başlangıcı olduğunda ise kısa olan kelime önce gelir.

Kelimelerde geçen harfleri, alfabetik sırada tek bir dize olarak döndürün. Listeye uyan birden fazla sıralama varsa, sözlük sıralamasında önce geleni döndürün. Hiçbir sıralama uymuyorsa "invalid" döndürün.

Fonksiyon

alienOrder(words: string-array) → string

wordsstring-array: bilinmeyen alfabeye göre sıralanmış sözcükler
Döndürürstring: sığan en küçük sıradaki harfler veya "invalid"

Kısıtlar

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Her sözcük yalnızca küçük İngilizce harflerden oluşur.
Aynı sözcük birden fazla kez geçebilir. ZORUNLU ÇIKTI BİÇİMİ: [Çevrilmiş içeriğiniz burada]

Örnekler

Girdi: words = ["tea", "ten", "ate", "act", "cat"]
Çıktı: "etacn"
Açıklama: tea ve ten ilk olarak a ve n harflerinde farklıdır; dolayısıyla a, n'den önce gelir. Diğer çiftler t'nin a'dan önce, t'nin c'den önce ve a'nın c'den önce gelmesini sağlar. Hiçbir kural e'den bahsetmediği için en küçük sıralamada önce e, sonra t, ardından a ve sonra da bu noktada ikisi de serbest olan c ve n yer alır; c önce gelir.

Girdi: words = ["bat", "tab", "tub", "bus"]
Çıktı: "invalid"
Açıklama: bat sözcüğünün tab sözcüğünden önce gelmesi, b'nin t'den önce gelmesini sağlar; tab sözcüğünün tub sözcüğünden önce gelmesi, a'nın u'dan önce gelmesini sağlar ve tub sözcüğünün bus sözcüğünden önce gelmesi, t'nin b'den önce gelmesini sağlar. b'nin t'den önce ve t'nin b'den önce olması aynı anda mümkün değildir, bu nedenle hiçbir sıralama uygun değildir.

Girdi: words = ["cooking", "cook"]
Çıktı: "invalid"
Açıklama: cook, cooking sözcüğünün başlangıcıdır; bu nedenle her alfabede önce gelir. Liste onu ikinci sıraya koyuyor ve harflerin hiçbir sıralaması bunu açıklayamaz.

Gönderirken +20 gizli test

Ek soru

Uydurma sırasının tek sıra olup olmadığını nasıl anlarsın?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Liste, alfabesini komşu sözcüklerin ilk kez farklılaştığı konumlarda gizler. Bu konumların her biri bir kural verir: x harfi, y harfinden önce gelir; kurallar da harfler üzerinde yönlü bir grafik oluşturur. Uygun bir sıralama, bu grafiğin topolojik sıralamasıdır. Listeyi imkânsız kılan iki durum vardır: kurallar arasında bir döngü bulunması ve bir sözcüğün kendi önekinden önce yer alması. Her adımda kullanılabilir en küçük harfi bir min-heap ile seçmek, sözlüksel olarak en küçük uygun sıralamayı verir.

Harflerin tüm sıralamalarını dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Yanıt, k farklı harfin bir sıralamasıdır. Bir sıralamayı doğrudan sınayabilirsiniz: Listedeki her komşu sözcük çifti, bu sıralamaya göre doğru sıradaysa liste sıralamaya uyar. Farklı oldukları ilk konumdaki iki harfi karşılaştırın; ilk sözcüğün harfi, sıralamada daha önce gelmelidir. Hiç farklılaşmıyorlarsa ilk sözcük daha uzun olmamalıdır. Komşular yeterlidir, çünkü sıralı olmak geçişli bir zincirdir: Her sözcük kendisinden sonrakinden küçük ya da ona eşitse listenin tamamı sıralıdır.

Şimdi sıralamaları küçükten büyüğe doğru gezin. Alfabetik sıradaki harflerle, yani tüm sıralamaların en küçüğüyle başlayın ve her seferinde bir sonraki büyük sıralamaya geçin (sonraki permütasyon). Testi geçen ilk sıralama, uyan en küçük düzendir. Hiçbiri geçmezse "invalid" döndürün.

Bu yöntem doğrudur ama gerçek girdilerde kullanılamayacak kadar yavaştır. k harfin k! sıralaması vardır: 5 harf 120, 10 harf 3.628.800 ve 26 harfin tamamı yaklaşık 4 × 10^26 sıralama verir. Her test, toplamda C karakter içeren ve en fazla 5 × 10^4 karaktere ulaşan listenin tamamını okur. Büyük testlerde uyan en küçük sıralama f veya z ile başlar; dolayısıyla ondan önce astronomik sayıda sıralama vardır ve hiçbir şey uymadığında arama her birini denemek zorundadır.

Algoritma

Farklı harfleri topla ve alfabetik sıraya koy.
Her harfin mevcut dizilişteki konumunu (sırasını) kaydet.
Her komşu çifti kontrol et: farklı olan ilk konumda, ilk kelimenin harfinin sırası daha küçük olmalıdır; farklılık yoksa ilk kelime daha uzun olmamalıdır.
Tüm çiftler koşulu sağlıyorsa dizilişi döndür. Aksi takdirde bir sonraki daha büyük dizilişe geç.
Bir sonraki diziliş yoksa "invalid" döndür.

from itertools import permutations


def fits(words, rank):
    # The list is sorted under rank when every neighbouring pair is in order.
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
        else:
            # One word starts the other: the shorter must come first.
            if len(first) > len(second):
                return False
    return True


def alienOrder(words):
    letters = sorted(set("".join(words)))
    # permutations() of a sorted list yields the orders from smallest to largest,
    # so the first order that fits is the answer.
    for order in permutations(letters):
        rank = {ch: i for i, ch in enumerate(order)}
        if fits(words, rank):
            return "".join(order)
    return "invalid"

Kahn algoritması ve minimum yığın

Sezgi

Sıralamayı tahmin etmek yerine kuralları listeden çıkarın. Yan yana duran iki sözcüğü alın ve farklı oldukları ilk konumu bulun. tea ve ten, t ve e harflerinde aynı olup a ve n harflerinde farklıdır; dolayısıyla a, n'den önce gelir. Bu çiftin verdiği mesaj bundan ibarettir. İlk farklılıktan sonraki harfler hiçbir şey ifade etmez: act, a harfi c'den önce geldiği için cat'ten önce gelir; act'teki c ve t harfleri, cat'teki a ve t harfleriyle hiçbir zaman karşılaştırılmaz. Yani her çift, bir harften diğerine giden bir kenar olmak üzere en fazla bir kural verir.

Farklı konumu olmayan bir çift, önek tuzağıdır. Bir sözcük diğerinin başlangıcıdır ve herhangi bir alfabede kısa olan önce gelmelidir. cook sözcüğünün cooking'den önce gelmesi uygundur ve hiçbir kural vermez. cooking sözcüğü cook'tan önce geliyorsa hiçbir zaman sıralanamaz; bu yüzden hemen "invalid" döndürün. Yalnızca farklı harfleri arayan bir döngü bu çiftte hiçbir şey bulamaz ve hiçbir alfabenin üretemeyeceği bir liste için sıralama döndürmeye devam eder.

Şimdi her kenara uyan bir harf sıralamasına, yani topolojik sıralamaya ihtiyacınız var. Kahn algoritması böyle bir sıralama oluşturur. Her harfe yönelen kenarları sayın (gelen derece), sayısı 0 olan bir harfi sıraya ekleyin, o harften çıkan kenarları kaldırın ve tekrarlayın. Bir döngüdeki harf, döngüde kendisinden önce gelen harften bir kenar almaya devam eder; bu nedenle sayısı hiçbir zaman 0 olmaz ve harf hiçbir zaman sıraya eklenmez. Sözcüklerde bulunan harflerden daha azı sıraya eklendiyse bir döngü vardır ve yanıt "invalid" olur.

En küçük sıralamayı elde etmek için sayısı 0 olan harfleri bir min-heap'te tutun ve her zaman en küçüğünü sıraya ekleyin. Bu açgözlü seçim güvenlidir. Kurallara uyan herhangi bir sıralamanın ilk harfinin gelen derecesi 0 olmalıdır; dolayısıyla sıraya eklenmeye hazır en küçük harf, mümkün olan en küçük ilk harftir. Bu harfi sıraya eklemek kenarları kaldırır ve başka bir harfin önünü asla kapatmaz: hazır olan her harf hazır kalır. Aynı mantık ikinci konum için de geçerlidir ve böyle devam eder. İlk örnekte e ve t başlangıçta sıraya eklenmeye hazırdır ve önce e gelir. Basit bir kuyruk da geçerli bir sıralama verir, ancak bu her zaman en küçük sıralama olmaz.

Maliyet, ilk farklılıkları bulmak için C karakterin tamamını kapsayan liste üzerinde tek bir geçiştir. k ≤ 26 harf olduğunda en fazla k² kenar bulunur; yinelenen bir kuralın yalnızca bir kez saklanması için bu kenarlar k'ye k tablosunda tutulur ve heap'te hiçbir zaman k'den fazla harf bulunmaz. Bu, O(C + k²) zaman demektir; en büyük testlerde birkaç milisaniye sürer.

Algoritma

Kelimelerde geçen her harfi işaretle.
Her komşu kelime çifti için, farklı olan ilk konumu bul. Böyle bir konum varsa ilk kelimedeki harften ikinci kelimedeki harfe bir kez kenar ekle. Böyle bir konum yoksa ve ilk kelime daha uzunsa "invalid" döndür.
Her harfin gelen kenarlarını say ve geçen, sayısı 0 olan her harfi bir min-yığına ekle.
En küçük harfi çıkar ve sona ekle. Bu harfin işaret ettiği her harfin sayısını azalt ve sayısı 0 olanları yığına ekle.
Yerleştirilen harf sayısı geçen harf sayısından azsa "invalid" döndür. Aksi takdirde yerleştirilen harfleri döndür.

import heapq


def alienOrder(words):
    # Letters are numbered 0 for 'a' up to 25 for 'z'.
    present = [False] * 26
    for word in words:
        for ch in word:
            present[ord(ch) - 97] = True
    # before[a][b] is True once you know letter a comes before letter b.
    before = [[False] * 26 for _ in range(26)]
    indegree = [0] * 26
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                # Only the first difference tells you anything.
                a, b = ord(x) - 97, ord(y) - 97
                if not before[a][b]:
                    before[a][b] = True
                    indegree[b] += 1
                break
        else:
            # No difference: one word starts the other, so the shorter must come first.
            if len(first) > len(second):
                return "invalid"
    # A min-heap of the letters with nothing left before them.
    heap = [c for c in range(26) if present[c] and indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        c = heapq.heappop(heap)
        order.append(chr(c + 97))
        for nxt in range(26):
            if before[c][nxt]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    heapq.heappush(heap, nxt)
    # A letter on a cycle never gets down to indegree 0, so it is never placed.
    if len(order) < sum(present):
        return "invalid"
    return "".join(order)

Tuzaklar ve uç durumlar

Buradaki yanlış yanıtların çoğu sessizdir: bir kuralı yanlış okumak yine de bir sıralama üretir, yalnızca yanlış sıralamayı.

Bir çiftte birden fazla kuralı dikkate almak. Yalnızca farklı olan ilk konum önemlidir. act ifadesinin cat ifadesinden önce gelmesi, a harfinin c harfinden önce geldiğini söyler; sonraki harfler hakkında hiçbir şey söylemez.
Önek tuzağını gözden kaçırmak. cooking ifadesinin cook ifadesinden önce gelmesinde farklı bir harf yoktur; bu yüzden yalnızca farklılıkları ele alan bir döngü hiçbir şey bulamaz ve bir sıralama döndürür. Yanıt "invalid" olmalıdır.
Hiçbir kuralda geçmeyen harfleri dışarıda bırakmak. İlk örnekte hiçbir kural e harfinden söz etmez, ancak e yanıtta yer almalıdır ve en küçük sıralamada ilk sırada bulunur.
Min-yığın yerine sıradan bir kuyruk kullanmak. Kuyrukla çalışan Kahn algoritması geçerli bir sıralama döndürür, ancak sözleşme en küçük sıralamayı ister.
Grafikte bir kez saklanan yinelenen bir kuralı, giriş derecesinde iki kez saymak. Bu durumda harfin giriş derecesi hiçbir zaman 0 olmaz ve geçerli bir liste döngü olarak raporlanır. Her kuralı bir kez saklayın ya da aynı sayıda ekleyip çıkarın.
Yan yana gelen iki eşit sözcüğü önek tuzağı olarak değerlendirmek. Bir sözcüğün ardından aynı sözcüğün gelmesi sıralamaya uygundur; yalnızca daha uzun bir sözcüğün kendi önekinden önce gelmesi imkânsızdır.

Sıkça sorulan sorular4

Alien Dictionary'nin zaman karmaşıklığı nedir?

O(C + k²); burada C, sözcüklerdeki toplam karakter sayısıdır ve k ≤ 26, farklı harflerin sayısıdır. Liste üzerinde yapılan tek bir geçiş, komşu her çiftin ilk farklılığını bulur ve Kahn algoritması en fazla k² kenarı ziyaret eder. Min-yığın O(k log k) ekler; bu, geri kalanına kıyasla küçüktür. Kenar tablosu O(k²) alan kullanır.

Neden yalnızca komşu kelimeleri karşılaştırıyoruz?

Sıralı olma özelliği geçişlidir: Her kelime kendisinden sonraki kelimeden büyük değilse, listenin tamamı sıralıdır. Dolayısıyla, aralarında uzaklık bulunan iki kelimeden çıkarabileceğin her kural, zaten aralarındaki komşu çiftlerden çıkar. Her kelime çiftini karşılaştırmak yeni bir bilgi sağlamaz ve n-1 karşılaştırma yerine O(n²) karşılaştırmaya mal olur.

Hazır harfler arasından en küçüğünü seçmek neden en küçük sıralamayı verir?

Geçerli her sıralama, hiçbir kuralın işaret etmediği bir harfle başlamalıdır. Bu tür en küçük harf, mümkün olan en küçük ilk harftir ve onu yerleştirmek yalnızca kenarları kaldırır; dolayısıyla hazır durumdaki diğer tüm harfler kullanılabilir kalır. Bu argümanı her konumda tekrarlamak, harf harf en küçük sıralamayı oluşturur. Bir min-heap, O(log k) sürede hazır durumdaki en küçük harfi verir.

Kendi önekinden önce gelen bir sözcük neden geçersizdir?

Her alfabede bir sözcük, kendi önekinden sonra gelir; çünkü karşılaştırma, bir fark bulamadan önce kısa olan sözcükteki harfleri tüketir. Bu nedenle cooking, harfler ne olursa olsun cook sözcüğünden önce gelirse sıralama bozulur ve hiçbir kural bunu düzeltemez. Kurallar arasında herhangi bir döngü olmadan bir listenin imkânsız olmasının tek yolu budur.

Python

def alienOrder(words):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

words = ["tea", "ten", "ate", "act", "cat"]

Beklenen

"etacn"