Isomorphic Strings

Q: למה צריך שתי מפות גיבוב עבור מחרוזות איזומורפיות?

מיפוי מ־ s אל t מזהה תו אחד מתוך s ששמו שונה בשתי דרכים. הוא אינו יכול לזהות שני תווים מתוך s ששמם שונה לאותו תו, כמו במקרה של ab ו־ aa . המיפוי מ־ t בחזרה אל s מזהה את המקרה הזה.

Q: האם איזומורפיזם הוא סימטרי?

כן. אפשר לבטל שינוי שם חד-חד-ערכי, כך שאם s משנה את שמה ל־ t , היפוך של כל השמות מחזיר את t ל־ s . isIsomorphic(s, t) ו־ isIsomorphic(t, s) תמיד מסכימות.

קלגיבוב

+10

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

פונקציה

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

sstring: המחרוזת שיש לשנות את שמה, אותיות וספרות
tstring: המחרוזת שאליה יש להגיע, באותו אורך כמו s
מחזירהboolean: נכון אם שינוי חד-חד-ערכי של שמות התווים של s נותן את t

אילוצים

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s ו-t מכילות רק אותיות באנגלית וספרות. אותיות גדולות וקטנות נחשבות לתווים שונים.

דוגמאות

קלט: s = "noon"t = "deed"
פלט: true
הסבר: שנה את השם של n ל־d ואת השם של o ל־e. כל המיקומים מתאימים לשינוי השמות הזה, ושתי האותיות מקבלות שמות שונים.

קלט: s = "moon"t = "deed"
פלט: false
הסבר: משמאל לימין, m הופכת ל־d ו־o הופכת ל־e, ואז גם n הייתה צריכה להפוך ל־d. שתי אותיות שונות לא יכולות לחלוק שם, ולכן התשובה היא false.

קלט: s = "r2d2"t = "c3p3"
פלט: true
הסבר: r הופך ל-c, 2 הופך ל-3 ו-d הופך ל-p. גם ספרות הן תווים, ושני מופעי 2 הופכים ל-3.

שאלת המשך

בהינתן רשימה של מילים, האם תוכלו לקבץ יחד את המילים שהן איזומורפיות זו לזו בלי להשוות בין כל זוג מילים?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

השווה כל זוג מיקומים

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

האינטואיציה

החלפת שמות שומרת על כך שתווים שווים יישארו שווים, ותווים שונים יישארו שונים. לכן, לכל זוג מיקומים i ו-j, s[i] == s[j] חייב להניב את אותה תשובה כמו t[i] == t[j]. גם התנאי הזה מספיק: אם כל זוגות המיקומים תואמים, החלפת כל תו של s בתו של t שבמיקומים שלו מוגדרת היטב, ולעולם לא נותנת לשני תווים אותו שם. ב-moon וב-deed, במיקומים 0 ו-3 יש אותיות שונות ב-s, אבל פעמיים d ב-t, ולכן התשובה היא false.

יש בערך n²/2 זוגות: 2 × 10^8 השוואות כאשר n = 2 × 10^4, אם אף זוג לא עוצר את הלולאה מוקדם.

אלגוריתם

עברו בלולאה על כל אינדקס i, ועל כל אחד מהם עברו על כל אינדקס מאוחר יותר j.
בדקו אם s[i] שווה ל־s[j], ואם t[i] שווה ל־t[j].
אם שתי התשובות שונות, החזירו false.
אחרי הזוג האחרון, החזירו true.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

שתי מפות, אחת לכל כיוון

האינטואיציה

בנו את המיפוי מחדש תוך כדי הקריאה. sToT מתעד לאיזו תו הפך כל תו של s, ו-tToS מתעד מהיכן הגיע כל תו של t. במיקום i, כאשר a = s[i] ו-b = t[i], או ששניהם חדשים ומקשרים ביניהם, או שהם כבר חייבים להצביע זה על זה.

מיפוי אחד אינו מספיק. עם sToT בלבד, moon ו-deed עוברים, כי אף אות של s אינה ממופה לשתי דרכים שונות. הבעיה היא שגם m וגם n הופכים ל-d, ובמיקום 3 tToS כבר מציין שמקורו של d הוא ב-m.

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

אלגוריתם

צור שתי מפות ריקות, sToT ו-tToS.
עבור כל אינדקס i, נגדיר a = s[i] ו-b = t[i].
אם a לא נמצא ב-sToT וגם b לא נמצא ב-tToS, נמפה את a אל b ואת b אל a.
אחרת, אם sToT[a] אינו b או tToS[b] אינו a, נחזיר false.
אחרי האינדקס האחרון, נחזיר true.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

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

שמירה על מיפוי יחיד מ־s ל־t. הוא מקבל את moon ואת deed, וגם את ab ואת aa.
השוואה של מספר הפעמים שכל תו מופיע. גם abcabc וגם xyzxzy משתמשים בשלושה תווים, פעמיים בכל אחד, ובכל זאת ה־b השני מופיע במקום שבו ה־z מופיע, בעוד שהראשון הופיע במקום שבו ה־y מופיע.
התייחסות לאותיות גדולות וקטנות כאילו הן זהות. ב־aA יש שני תווים שונים, ולכן הוא לא יכול להפוך ל־bb.
הגבלת גודל מערכי המיפוי לאותיות a עד z בלבד. אותיות גדולות וספרות נמצאות מחוץ לטווח הזה; השתמשו בקוד התו המלא כאינדקס, עם 128 כניסות.

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

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

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

למה צריך שתי מפות גיבוב עבור מחרוזות איזומורפיות?

מיפוי מ־s אל t מזהה תו אחד מתוך s ששמו שונה בשתי דרכים. הוא אינו יכול לזהות שני תווים מתוך s ששמם שונה לאותו תו, כמו במקרה של ab ו־aa. המיפוי מ־t בחזרה אל s מזהה את המקרה הזה.

האם איזומורפיזם הוא סימטרי?

כן. אפשר לבטל שינוי שם חד-חד-ערכי, כך שאם s משנה את שמה ל־t, היפוך של כל השמות מחזיר את t ל־s. isIsomorphic(s, t) ו־isIsomorphic(t, s) תמיד מסכימות.

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

החליפו כל תו במיקום שבו הוא מופיע לראשונה והשוו בין התוצאות. גם noon וגם deed הופכים ל־0 1 1 0, ואילו moon הופך ל־0 1 1 3. זמן הריצה הוא גם O(n), ונדרש זיכרון של O(n) עבור שתי התבניות.

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

s = "noon"
t = "deed"

הפלט הצפוי

true