אתגר תכנותי: מילון חייזרי

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

המטרה היא לגלות את סדר האותיות.

זהו אתגר Leetcode מספר 269: Alien Dictionary. זו דוגמה קלאסית לבעיה שניתן לפתור באמצעות מיון טופולוגי, וזהו תרגיל מצוין למי שרוצה להתחזק באלגוריתמים מבוססי גרפים.

האתגר

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

עליך להסיק את סדר האותיות של השפה.

הנחות:

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

דוגמאות

דוגמה 1:

Input: ["z","a"]
Output: "za"

• כי החוק הוא ש- 'z' בא לפני 'a'.

דוגמה 2:

Input: ["mrp","mrf","vr","vpp","rfpp"]
Output: "mvrpf"

ניתן להסיק את החוקים הבאים:

• 'p' -> 'f' (כי "mrp" בא לפני "mrf")
• 'm' -> 'v' (כי "mrf" בא לפני "vr")
• 'r' -> 'p' (כי "vr" בא לפני "vpp")

דוגמה 3:

Input: ["i", "v", "i"]
Output: ""

• כי יוצר מעגל ( 'i' < 'v' < 'i'), מה שלא מאפשר לקבוע איזו אות קודמת. לכן מחזירים מחרוזת ריקה.

רמז לפתרון

נתייחס לכל אות כאל צומת בגרף. חוק כמו 'a' בא לפני 'a' יתורגם לקשת a → b.
אחרי שנבנה את הגרף לפי המידע מהמילים, נבצע מיון טופולוגי כדי לקבל סדר אפשרי של האותיות.

נשתמש באלגוריתם של Kahn - אלגוריתם מבוסס BFS (חיפוש לרוחב). אם אתם לא מכירים אותו, מוזמנים לקרוא הסבר מצוין על מיון טופולוגי כאן.

פתרון ב-Python

from collections import deque

def alien_dictionary(words):
    def topological_sort(letters, prerequisites):
        sorted_list = []
        in_degrees = {letter: 0 for letter in letters}
        adj_list = {letter: [] for letter in letters}

        for letter, pre in prerequisites:
            adj_list[pre].append(letter)
            in_degrees[letter] += 1

        q = deque([letter for letter in letters if in_degrees[letter] == 0])

        while q:
            current = q.popleft()
            sorted_list.append(current)
            for neighbor in adj_list[current]:
                in_degrees[neighbor] -= 1
                if in_degrees[neighbor] == 0:
                    q.append(neighbor)

        return ''.join(sorted_list) if len(sorted_list) == len(letters) else ""

    letters = set(c for word in words for c in word)
    dependencies = []

    for i in range(1, len(words)):
        prev_word, curr_word = words[i-1], words[i]
        min_len = min(len(prev_word), len(curr_word))
        found_order = False
        for j in range(min_len):
            if prev_word[j] != curr_word[j]:
                dependencies.append((curr_word[j], prev_word[j]))  # `curr` depends on `prev`
                found_order = True
                break
        if not found_order and len(curr_word) < len(prev_word):
            return ""  # Prefix rule violated

    return topological_sort(letters, dependencies)

הסבר החלק הקריטי

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

dependencies = []

for i in range(1, len(words)):
    prev_word, curr_word = words[i-1], words[i]
    min_len = min(len(prev_word), len(curr_word))
    found_order = False
    for j in range(min_len):
        if prev_word[j] != curr_word[j]:
            dependencies.append((curr_word[j], prev_word[j]))
            found_order = True
            break
    if not found_order and len(curr_word) < len(prev_word):
        return ""  # הפרת תנאי הקידומת

נסביר:

• משווים כל זוג מילים עוקבות.
• מוצאים את האות הראשונה ששונה ביניהן.
• עוצרים ברגע שמצאנו אות שונה כי לא צריך לבדוק מעבר.
• אם כל האותיות זהות והמילה השנייה קצרה יותר זו הפרה של "תנאי הקידומת".

אלגוריתם Kahn למיון תלויות על קצה המזלג

אחרי שחילצנו את רשימת התלויות:

1. יוצרים גרף שבו כל אות היא צומת.
2. מוצאים את כמות האותיות בהם תלויה כל אות in-degree.
3. מתחילים מאותיות ללא דרישות מוקדמות in-degree == 0
4. יוצרים רשימה של אותיות ללא דרישות מקדימות.

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

ניתוח סיבוכיות

נניח ש־N הוא מספר המילים, ו־K הוא מספר האותיות.

• זמן ריצה: O(K + E)
• K הוא מספר האותיות השונות.
• E הוא מספר חוקי הסדר (קשתות בגרף).
• זיכרון: O(K + E)
  עבור ייצוג הגרף ומעקב אחר in-degree.

הפתרון מאוד יעיל. גם לקלטים גדולים.

לסיכום

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

שינעם לך קידודך!

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

מיון טופולוגי באמצעות אלגוריתם Kahn

הבנת אלגוריתם חיפוש לרוחב - BFS - סריקה של גרפים ומציאת הנתיב הקצר ביותר

יישום תורת הגרפים בפייתון - חלק א

יישום רשימת סמיכויות adjacency list - חלק ב בסדרה על גרפים

Pyviz - ספרייה להצגת גרפים אינטראקטיביים

General Tree data structure עץ נתונים

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים