Group Anagrams

Q: האם מפתח לספירת אותיות מהיר יותר ממיון כל מילה?

מפתח ספירה, כלומר 26 הספירות של האותיות הכתובות כטקסט כגון 1#0#2#… , דורש זמן O(k) במקום O(k log k) , ולכן הוא עדיף במילים ארוכות. במילים שאורכן עד 8 אותיות, המיון מהיר באותה מידה, והמיון האלפביתי של הפלט עולה יותר מכל אחד מהמפתחות. שני המפתחות נכונים, כי לשתי מילים יש אותן ספירות בדיוק כאשר האותיות הממוינות שלהן זהות.

בינוניגיבוב מיון

+10

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

מילה שמופיעה פעמיים תופיע פעמיים בקבוצה שלה, ומילה שאין לה אנגרמה תיצור קבוצה של מילה אחת. סדר אלפביתי פירושו סדר מילוני: aab מופיעה לפני ab, ו-ab לפני abc.

פונקציה

groupAnagrams(strs: string-array) → string-array

strsstring-array: המילים לקיבוץ, אותיות קטנות בלבד
מחזירהstring-array: מחרוזת אחת לכל קבוצה: המילים שלה ממוינות ומחוברות ברווחים, והקבוצות מסודרות לפי המילה הראשונה שלהן

אילוצים

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
כל מילה מכילה אותיות אנגליות קטנות בלבד.

דוגמאות

קלט: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
פלט: ["apple", "enlist listen silent", "notes onset stone tones"]
הסבר: המילים enlist, listen ו־silent משתמשות כל אחת באותיות e, i, l, n, s ו־t פעם אחת. המילים notes, onset, stone ו־tones חולקות את האותיות e, n, o, s ו־t, ו־apple אינה תואמת לשום דבר. לפי המילה הראשונה, הקבוצות מופיעות בסדר apple, enlist, notes.

קלט: strs = ["race", "arc", "care", "car", "acre"]
פלט: ["acre care race", "arc car"]
הסבר: ל־acre, ל־care ול־race יש את האותיות a, c, e ו־r במשותף. ב־arc וב־car אין e, ולכן הם יוצרים קבוצה משלהם. acre מופיעה לפני arc, כי האות c מופיעה לפני r באות השנייה.

קלט: strs = ["b", "a", "b"]
פלט: ["a", "b b"]
הסבר: שני העותקים של b הם אנגרמות זה של זה, ושניהם נשארים בקבוצה. ל-a אין בן זוג, והוא מופיע ראשון.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

השוו כל מילה לכל קבוצה

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

האינטואיציה

היותן של מילים אנגרמות היא תכונה טרנזיטיבית: אם stone תואמת ל־notes ו־notes תואמת ל־tones, אז stone תואמת ל־tones. לכן מילה חדשה לעולם לא צריכה להתאים לכל איבר בקבוצה. השוואה שלה למילה הראשונה בקבוצה קובעת אם היא שייכת אליה.

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

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

העלות היא הסריקה. כשאין שתי מילים שהן אנגרמות, משווים כל מילה לכל קבוצה שלפניה: 4000 מילים יוצרות בערך 4000 × 3999 / 2 ≈ 8 × 10^6 השוואות, שכל אחת מהן בודקת עד 8 אותיות ו־26 מונים. זה איטי מדי עבור Python, Lua ו־R במבחנים הגדולים ביותר, והעבודה גדלה כריבוע של גודל הרשימה, כך שהיא תכשיל כל שפה עם 10^5 מילים.

אלגוריתם

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

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

קבץ לפי אותיות ממוינות במפת גיבוב

האינטואיציה

במקום לשאול לאיזו קבוצה מתאימה מילה, חשבו את שם הקבוצה מתוך המילה עצמה. מיון האותיות של מילה יוצר אותו טקסט עבור כל המילים שהן אנגרמות שלה: listen, silent ו-enlist הופכות כולן ל-eilnst, ואילו stone הופכת ל-enost. שתי מילים חולקות צורה ממוינת בדיוק כאשר הן מכילות את אותן אותיות באותו מספר פעמים, וזוהי ההגדרה של אנגרמה. לכן הצורה הממוינת היא מפתח קנוני לקבוצה.

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

כדי לשמור על הסדר, מיינו את הקלט לפני הקיבוץ, כמו בגישה הראשונה. המילים מגיעות בסדר אלפביתי, ולכן כל רשימה מתמלאת לפי הסדר, ומפתח נכנס למפה כאשר המילה הראשונה בקבוצה שלו מגיעה. מפות ששומרות על סדר ההכנסה (מילון Python, ‏Map של JavaScript, ‏LinkedHashMap של Java, ‏map של Dart, גיבובי Ruby ומערכים של PHP) מחזירות את הקבוצות בסדר הזה. כאשר למפה אין סדר, שמרו את האינדקס של כל קבוצה במפה ואת הקבוצות עצמן ברשימה.

מיון הקלט דורש בערך n log n השוואות של עד k אותיות, כלומר בערך 5 × 10^4 השוואות בין מילים עבור 4000 מילים, במקום 8 × 10^6. בניית המפתחות מוסיפה O(n · k log k), וזה מעט ביחס לכך כי k ≤ 8.

אלגוריתם

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

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

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

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

מיון הקבוצות לפי המפתח שלהן במקום לפי המילה הראשונה שלהן. מפתח הוא סידור מחדש בסדר הקטן ביותר של האותיות במילים, ולא אחת מהן: עבור ["cab", "bad"] המפתחות הם abc ו-abd, מה שהיה מציב את cab ראשונה, אבל לפי המילה הראשונה bad באה קודם.
איסוף המילים בקבוצה. ["b", "a", "b"] חייב להניב b b; קבוצה שומרת עותק אחד בלבד.
מפתח שנבנה מהאותיות הייחודיות בלבד. ab ו-aabb משתמשות באותן שתי אותיות, אבל ב-aabb יש שתיים מכל אחת, ולכן הן אינן אנגרמות.
מפתח שמחבר את קודי האותיות. ל-ad ול-bc יש אותו סכום, ולכן סכום ממזג מילים שאין להן אף אות משותפת.
מיון כל קבוצה אבל לא הקלט, ואז שכחה למיין את הקבוצות. כך סדר ההכנסה הוא סדר הקלט, ולא סדר המילים הראשונות.
חיבור ידני והשארת רווח בתחילת המחרוזת של קבוצה או בסופה.

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

מהי סיבוכיות הזמן של קיבוץ אנגרמות?

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

האם מפתח לספירת אותיות מהיר יותר ממיון כל מילה?

מפתח ספירה, כלומר 26 הספירות של האותיות הכתובות כטקסט כגון 1#0#2#…, דורש זמן O(k) במקום O(k log k), ולכן הוא עדיף במילים ארוכות. במילים שאורכן עד 8 אותיות, המיון מהיר באותה מידה, והמיון האלפביתי של הפלט עולה יותר מכל אחד מהמפתחות. שני המפתחות נכונים, כי לשתי מילים יש אותן ספירות בדיוק כאשר האותיות הממוינות שלהן זהות.

למה לא להשתמש בסכום של קודי האותיות בתור המפתח?

אותיות שונות יכולות להסתכם לאותו סכום: ‏a + d שווה ל־b + c, ולכן ad ו־bc יהיו באותה קבוצה. מפתח חייב להיות זהה עבור אנגרמות ושונה עבור כל דבר אחר, והמיון של האותיות או הספירה המלאה של כל אות מבטיחים זאת. גם הכפלה של מספר ראשוני אחד לכל אות מדויקת, אבל כשמשתמשים ב־101 עבור z, מילה שמורכבת מעשרה z-ים כבר גורמת לגלישה של מספר שלם בן 64 סיביות.

למה למיין את הקלט לפני הקיבוץ?

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

Python

def groupAnagrams(strs):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

צפוי

["apple", "enlist listen silent", "notes onset stone tones"]