Valid Anagram

Q: מהי סיבוכיות הזמן של Valid Anagram?

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

Q: האם עדיף למיין או לספור כשבודקים אם שתי מילים הן אנגרמה?

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

קלגיבוב מיון

+10

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

פונקציה

isAnagram(s: string, t: string) → boolean

sstring: המחרוזת הראשונה, אותיות קטנות
tstring: המחרוזת להשוואה מול s
מחזירהboolean: true אם t משתמשת בדיוק באותיות של s, כל אחת באותו מספר פעמים

אילוצים

1 ≤ s.length, t.length ≤ 2 × 10⁴
s ו-t מכילות רק אותיות קטנות באנגלית (a עד z).
ייתכן ששני האורכים יהיו שונים.

דוגמאות

קלט: s = "listen"t = "silent"
פלט: true
הסבר: בשתי המילים יש אחת מכל האותיות e, i, l, n, s ו-t, לכן silent היא listen כשהאותיות שלה מסודרות מחדש.

קלט: s = "aabb"t = "abbb"
פלט: false
הסבר: האורכים תואמים ושניהם משתמשים רק ב-a וב-b, אבל ב-aabb יש שני a, וב-abbb יש אחד. הכמויות צריכות להיות תואמות, ולא רק האותיות.

קלט: s = "cat"t = "cast"
פלט: false
הסבר: ל־cast יש ארבע אותיות ול־cat יש שלוש, ולכן שום סידור מחדש של cat לא יכול לאיית אותו.

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

שאלת המשך

מה אם המחרוזות יכלו להכיל כל תו Unicode במקום a עד z? איך היית משנה את הספירה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

אנגרמה שומרת על מספר המופעים של כל אות ומשליכה את הסדר. לכן צריך סיכום של כל מחרוזת ששוכח היכן היו האותיות, אבל זוכר כמה יש מכל אחת מהן. מיון יוצר את הסיכום הזה ב־O(n log n); טבלה של 26 מונים יוצרת אותו במעבר אחד.

מיינו את שתי המחרוזות

האינטואיציה

מיון מסדר את האותיות של מחרוזת בסדר אלפביתי ומוחק את המידע על המקום שבו כל אות התחילה. listen ממוינת ל־eilnst, וכך גם silent, לכן הן אנגרמות. aabb נשארת aabb ו־abbb נשארת abbb; הן שונות באינדקס 1, ולכן הן אינן אנגרמות.

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

השוו תחילה את האורכים: מחרוזות באורכים שונים לעולם אינן אנגרמות, ואפשר לדלג על שני המיונים. מיון דורש זמן O(n log n), ורוב השפות ממיינות עותק של התווים, מה שדורש O(n) מקום נוסף. עבור n = 2 × 10^4 זה מהיר, אבל גישת הספירה דורשת פחות עבודה.

אלגוריתם

אם אורכי s ו־t שונים, החזר false.
העתק את התווים של כל מחרוזת למערך.
מיין את שני המערכים.
החזר true אם המערכים הממוינים שווים, איבר אחר איבר.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

ספרו כל אות

האינטואיציה

יכולות להופיע רק 26 אותיות, לכן שמור מונה אחד לכל אות במערך בגודל 26, עם האינדקס 0 עבור a והאינדקס 25 עבור z. האינדקס של אות הוא קוד התו שלה פחות הקוד של a. עבור על s והוסף 1 למונה של כל אות, ואז עבור על t והפחת 1.

אפשר לעצור מוקדם: מונה קטן מ-0 פירושו ש-t השתמשה באות הזו יותר פעמים מאשר היא מופיעה ב-s. עבור aabb ו-abbb, אחרי s המונים מראים a: 2 ו-b: 2. לאחר מכן t משתמשת ב-b שלוש פעמים; בפעם השלישית המונה של b יורד ל-1-, ומחזירים מיד את false.

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

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

אלגוריתם

אם האורכים של s ו-t שונים, החזר false.
צור מערך של 26 אפסים.
עבור כל אות ב-s, הוסף 1 למונה שלה.
עבור כל אות ב-t, הפחת 1 מהמונה שלה; אם הוא יורד מתחת ל-0, החזר false.
החזר true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

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

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

השוואת קבוצות האותיות. גם aabb וגם abbb מכילות בדיוק את a ואת b, ובכל זאת הן אינן אנגרמות.
בדיקה שכל אות ב-t מופיעה במקום כלשהו ב-s בלי לסמן אותה כבדוקה. aab ו-abb עוברות את הבדיקה הזו בשני הכיוונים.
דילוג על בדיקת האורך בגרסה שמשתמשת בספירה. עם s = ab ו-t = a, אף מונה לא יורד מתחת ל-0, ולכן הקוד יחזיר בטעות true.
שימוש בקוד התו הגולמי כאינדקס במערך המונים. הערך של a הוא 97, הרבה מעבר לסוף של מערך באורך 26; יש להפחית תחילה את הקוד של a. ב-Lua וב-R יש להוסיף 1, מכיוון שהמערכים שלהן מתחילים באינדקס 1.

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

מהי סיבוכיות הזמן של Valid Anagram?

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

האם עדיף למיין או לספור כשבודקים אם שתי מילים הן אנגרמה?

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

איך בודקים אנגרמות שמכילות תווי Unicode?

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

למה להשתמש במערך מונים אחד במקום בשניים?

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

Python

def isAnagram(s, t):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "listen"
t = "silent"

צפוי

true