Alien Dictionary

+10

רשימת מילים ממוינת לפי אלפבית שאינך מכיר: 26 האותיות האנגליות הקטנות בסדר סודי כלשהו. משווים בין מילים בדרך הרגילה. המיקום הראשון שבו שתי מילים שונות קובע איזו מהאותיות מופיעה קודם באלפבית, וכשאחת המילים היא תחילתה של האחרת, המילה הקצרה יותר מופיעה קודם.

החזר את האותיות שמופיעות במילים כמחרוזת אחת, לפי סדר האלפבית. אם כמה סדרים מתאימים לרשימה, החזר את הסדר שמופיע ראשון בסדר מילוני רגיל. אם שום סדר לא מתאים, החזר "invalid".

פונקציה

alienOrder(words: string-array) → string

wordsstring-array: המילים, ממוינות לפי האלפבית הלא ידוע
מחזירהstring: האותיות בסדר הקטן ביותר שמתאים, או "invalid"

אילוצים

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
כל מילה מכילה רק אותיות אנגליות קטנות.
ייתכן שאותה מילה תופיע יותר מפעם אחת.

דוגמאות

קלט: words = ["tea", "ten", "ate", "act", "cat"]
פלט: "etacn"
הסבר: tea ו-ten נבדלות לראשונה ב-a וב-n, ולכן a מופיעה לפני n. הזוגות האחרים נותנים t לפני a, t לפני c ו-a לפני c. שום כלל אינו מזכיר את e, ולכן הסדר הקטן ביותר מציב אותה ראשונה, אחריה t, אחר כך a, ואז c ו-n, ששתיהן חופשיות בשלב הזה, כאשר c ראשונה.

קלט: words = ["bat", "tab", "tub", "bus"]
פלט: "invalid"
הסבר: bat לפני tab מציב את b לפני t, tab לפני tub מציב את a לפני u, ו-tub לפני bus מציב את t לפני b. b לפני t ו-t לפני b אינם יכולים להתקיים בו-זמנית, ולכן אין סדר שמתאים.

קלט: words = ["cooking", "cook"]
פלט: "invalid"
הסבר: cook היא ההתחלה של cooking, ולכן בכל אלפבית היא באה ראשונה. ברשימה היא מופיעה במקום השני, דבר שאי אפשר להסביר באמצעות שום סדר של האותיות.

+20 בדיקות נסתרות בשליחה

שאלת המשך

איך תוכל לדעת אם סדר ההתאמה הוא היחיד?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

הרשימה מסתירה את האלפבית שלה במקומות שבהם מילים שכנות שונות לראשונה. כל מקום כזה מספק כלל אחד: האות x לפני האות y, והכללים יוצרים גרף מכוון על האותיות. סדר מתאים הוא סדר טופולוגי של הגרף הזה. שני דברים הופכים את הרשימה לבלתי אפשרית: מעגל בין הכללים, ומילה שמופיעה לפני הקידומת שלה עצמה. הצבת האות הזמינה הקטנה ביותר בכל שלב, באמצעות ערימת מינימום, נותנת את הסדר המתאים הקטן ביותר.

נסו כל סדר אפשרי של האותיות

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

התשובה היא סידור כלשהו של k האותיות השונות. אפשר לבדוק סידור אחד ישירות: הרשימה מתאימה לו אם כל זוג מילים סמוכות מופיע בו לפי הסדר. משווים בין שתי המילים במקום הראשון שבו הן שונות; האות במילה הראשונה חייבת להופיע מוקדם יותר בסידור. אם הן אינן שונות כלל, המילה הראשונה לא יכולה להיות ארוכה יותר. מספיק לבדוק מילים סמוכות, כי מיון הוא שרשרת: אם כל מילה קטנה או שווה למילה שאחריה, הרשימה כולה ממוינת.

כעת עוברים על הסידורים מהקטן לגדול. מתחילים באותיות בסדר אלפביתי, שהוא הסידור הקטן ביותר, ובכל פעם עוברים לסידור הגדול הבא (התמורה הבאה). הסידור הראשון שעובר את הבדיקה הוא הסדר הקטן ביותר שמתאים. אם אף סידור לא עובר, מחזירים "invalid".

זה נכון, אבל לא מעשי כלל עבור קלט אמיתי. ל-k אותיות יש k! סידורים: 5 אותיות נותנות 120, 10 נותנות 3,628,800, וכל 26 האותיות נותנות בערך 4 × 10^26. בכל בדיקה קוראים את הרשימה כולה, C תווים בסך הכול ועד 5 × 10^4. בבדיקות הגדולות, הסדר המתאים הקטן ביותר מתחיל ב-f או ב-z, ולכן מספר אסטרונומי של סידורים מופיע לפניו, וכשאין סידור מתאים החיפוש צריך לבדוק את כולם.

אלגוריתם

אסוף את האותיות השונות וסדר אותן בסדר אלפביתי.
רשום את המיקום של כל אות (הדירוג שלה) בסידור הנוכחי.
בדוק כל זוג סמוך: במיקום הראשון שבו האותיות שונות, האות במילה הראשונה צריכה להיות בעלת הדירוג הנמוך יותר; אם אין מיקום כזה, המילה הראשונה לא צריכה להיות ארוכה יותר.
אם כל הזוגות עומדים בתנאי, החזר את הסידור. אחרת, עבור לסידור הבא בגודלו.
כשאין סידור הבא, החזר "invalid".

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"

האלגוריתם של קאהן עם ערימת מינימום

האינטואיציה

קראו את הכללים מתוך הרשימה במקום לנחש את הסדר. קחו שתי מילים סמוכות ומצאו את המיקום הראשון שבו הן שונות. tea ו־ten זהות ב־t וב־e ושונות ב־a וב־n, ולכן a מופיעה לפני n. זה כל המסר של הזוג. האותיות שאחרי ההבדל הראשון לא אומרות דבר: act מופיעה לפני cat כי a מופיעה לפני c, ולעולם לא משווים בין c ו־t שאחריה ב־act לבין a ו־t שב־cat. לכן כל זוג נותן לכל היותר כלל אחד, קשת מאות אחת לאחרת.

זוג שאין בו מיקום שונה הוא מלכודת הקידומת. מילה אחת היא תחילתה של האחרת, והקצרה חייבת להופיע קודם בכל אלפבית. cook לפני cooking זה תקין ולא נותן כלל. אי אפשר למיין את cooking לפני cook, ולכן יש להחזיר מיד את "invalid". לולאה שרק מחפשת אותיות שונות לא תמצא דבר בזוג הזה, ותמשיך להחזיר סדר עבור רשימה ששום אלפבית לא יכול להפיק.

עכשיו דרוש לכם סדר של האותיות שמכבד כל קשת — סדר טופולוגי. האלגוריתם של קאהן בונה סדר כזה. ספרו את הקשתות שמצביעות אל כל אות (דרגת הכניסה שלה), הוסיפו אות שמספרן 0, הסירו את הקשתות היוצאות שלה וחזרו על הפעולה. לאות שנמצאת במחזור תמיד נשארת קשת מהאות שלפניה במחזור, ולכן מספר הקשתות שלה לעולם לא מגיע ל־0 והיא לעולם לא מתווספת. אם נוספו פחות אותיות ממספר האותיות שמופיעות במילים, יש מחזור והתשובה היא "invalid".

כדי לקבל את הסדר הקטן ביותר, שמרו את האותיות שמספר הקשתות שלהן הוא 0 בערימת מינימום והוסיפו תמיד את הקטנה ביותר. הבחירה החמדנית הזאת בטוחה. לאות הראשונה בכל סדר מתאים יש דרגת כניסה 0, ולכן האות הקטנה ביותר שמוכנה היא האות הראשונה הקטנה ביותר האפשרית. הוספתה מסירה קשתות ולעולם אינה חוסמת אות אחרת: כל אות שהייתה מוכנה נשארת מוכנה. אותו נימוק חל על המיקום השני, וכן הלאה. בדוגמה הראשונה גם e וגם t מוכנות בהתחלה, ו־e מופיעה ראשונה. גם תור רגיל היה נותן סדר תקין, אך לא תמיד את הקטן ביותר.

העלות היא מעבר אחד על הרשימה, שבה C תווים בסך הכול, כדי למצוא את ההבדלים הראשונים. כש־k ≤ 26 אותיות, יש לכל היותר k² קשתות, הנשמרות בטבלה בגודל k על k כך שכלל חוזר נשמר פעם אחת, והערימה מכילה לכל היותר k אותיות. סיבוכיות הזמן היא O(C + k²), כמה אלפיות השנייה בבדיקות הגדולות ביותר.

אלגוריתם

סמנו כל אות שמופיעה במילים.
עבור כל זוג מילים סמוכות, מצאו את המיקום הראשון שבו הן שונות. אם יש כזה, הוסיפו פעם אחת את הקשת מהאות במילה הראשונה לאות במילה השנייה. אם אין כזה והמילה הראשונה ארוכה יותר, החזירו "invalid".
ספרו את הקשתות הנכנסות לכל אות והכניסו לערימת מינימום כל אות שמופיעה ושמספר הקשתות הנכנסות שלה הוא 0.
הוציאו את האות הקטנה ביותר והוסיפו אותה לסוף. הפחיתו את המספר של כל אות שאליה היא מצביעה, והכניסו לערימה כל אות שהמספר שלה מגיע ל-0.
אם הוצבו פחות אותיות ממספר האותיות שמופיעות, החזירו "invalid". אחרת החזירו את האותיות שהוצבו.

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)

מלכודות ומקרי קצה

רוב התשובות השגויות כאן הן שגיאות שקטות: כלל שנקרא לא נכון עדיין מניב סדר כלשהו, אבל הוא שגוי.

לקיחת יותר מכלל אחד מתוך זוג. רק המיקום הראשון שבו יש הבדל נחשב. act לפני cat קובע ש־a לפני c ולא אומר דבר על האותיות שאחריהן.
החמצת מלכודת הקידומת. cooking לפני cook אינו כולל אות שונה, ולכן לולאה שמטפלת רק בהבדלים לא רואה דבר ומחזירה סדר. התשובה היא "invalid".
השמטת אותיות שאינן מופיעות באף כלל. בדוגמה הראשונה שום כלל לא מזכיר את e, ובכל זאת היא צריכה להופיע בתשובה, והסדר הקטן ביותר מציב אותה ראשונה.
שימוש בתור רגיל במקום בערימת מינימום. האלגוריתם של Kahn עם תור מחזיר סדר תקין, אבל החוזה דורש את הסדר הקטן ביותר.
ספירת כלל שחוזר פעמיים בדרגת הכניסה, אך שמירתו פעם אחת בגרף. לכן האות לעולם לא מגיעה ל־0, ורשימה תקינה מדווחת כמעגל. יש לשמור כל כלל פעם אחת, או להוסיף ולהסיר אותו אותו מספר פעמים.
התייחסות לשתי מילים שכנות זהות כאל מלכודת קידומת. מילה שאחריה מופיעה אותה מילה נמצאת בסדר תקין; רק מילה ארוכה יותר שמופיעה לפני הקידומת שלה עצמה היא בלתי אפשרית.

שאלות נפוצות4

מהי סיבוכיות הזמן של מילון החייזרים?

O(C + k²), כאשר C הוא מספר התווים הכולל במילים ו־k ≤ 26 הוא מספר האותיות השונות. מעבר אחד על הרשימה מוצא את ההבדל הראשון בכל זוג שכנים, והאלגוריתם של Kahn עובר על לכל היותר k² קשתות. ערימת המינימום מוסיפה O(k log k), וזה מעט ביחס לשאר. טבלת הקשתות דורשת O(k²) מקום.

למה להשוות רק בין מילים סמוכות?

סדר הוא יחס טרנזיטיבי: אם כל מילה קטנה או שווה למילה שאחריה, כל הרשימה ממוינת. לכן כל כלל שאפשר להסיק משתי מילים המרוחקות זו מזו נובע כבר מהזוגות הסמוכים שביניהן. השוואה בין כל זוג מילים אינה מוסיפה מידע, ומצריכה O(n²) השוואות במקום n-1.

למה בחירה באות הקטנה ביותר שמוכנה נותנת את הסדר הקטן ביותר?

כל סדר מתאים חייב להתחיל באות שאף כלל אינו מצביע עליה. לכן, האות הקטנה ביותר כזאת היא האות הראשונה הקטנה ביותר האפשרית, והצבתה רק מסירה קשתות, כך שכל אות מוכנה אחרת נשארת זמינה. חזרה על הטיעון בכל מיקום בונה את הסדר הקטן ביותר אות אחר אות. ערימת מינימום מספקת לך את האות המוכנה הקטנה ביותר בזמן O(log k).

למה מילה שמופיעה לפני הקידומת של עצמה אינה תקינה?

בכל אלפבית, מילה מופיעה אחרי הקידומת שלה, כי ההשוואה מגיעה לסוף האותיות במילה הקצרה יותר לפני שהיא מוצאת הבדל. לכן cooking לפני cook אינו בסדר הנכון, יהיו האותיות אשר יהיו, ושום כלל לא יכול לתקן זאת. זו הדרך היחידה שבה רשימה יכולה להיות בלתי אפשרית בלי שיהיה מעגל כלשהו בין הכללים שלה.

Python

def alienOrder(words):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

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

צפוי

"etacn"