Permutation in String

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

בשימוש בחלון הזזה, הסיבוכיות היא O(m + n) , כאשר m הוא האורך של s1 ו- n הוא האורך של s2 . סופרים את s1 פעם אחת, ואז כל אות ב- s2 נכנסת לחלון פעם אחת ויוצאת ממנו פעם אחת. ספירה מחדש של כל חלון מההתחלה עולה O(n · m) במקום זאת.

Q: האם תמורה במחרוזת זהה למציאת אנגרמה בתוך מחרוזת?

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

Q: למה חלון ההזזה הוא בגודל קבוע כאן?

בכל תמורה של s1 יש בדיוק m אותיות, ולכן רק חלונות באורך m יכולים להתאים. בבעיות כמו תת־המחרוזת הארוכה ביותר ללא חזרות, החלון מתרחב ומתכווץ; כאן שני הקצוות נעים יחד, צעד אחד בכל פעם.

בינוניחלון נע גיבוב

+10

תמורה של מחרוזת משתמשת באותן אותיות בכל סדר שהוא, כל אחת מהן באותו מספר פעמים כמו במחרוזת המקורית: tar, rat ו-art הן תמורות זו של זו. נתונות לך שתי מחרוזות s1 ו-s2 המורכבות מאותיות אנגליות קטנות. החזר true אם תמורה כלשהי של s1 מופיעה ב-s2 כתת-מחרוזת (רצף של תווים עוקבים), ואחרת החזר false.

פונקציה

checkInclusion(s1: string, s2: string) → boolean

s1string: האותיות שיש לסדר מחדש
s2string: המחרוזת שבה יש לחפש
מחזירהboolean: נכון אם תת־מחרוזת של s2 היא סידור מחדש של s1

אילוצים

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 ו-s2 מכילים רק אותיות קטנות באנגלית (a עד z).
s1 עשויה להיות ארוכה יותר מ־s2.

דוגמאות

קלט: s1 = "tar"s2 = "smartphone"
פלט: true
הסבר: תת־המחרוזת art באינדקסים 2 עד 4 של smartphone מכילה a אחד, r אחד ו־t אחד — אותן אותיות כמו ב־tar.

קלט: s1 = "noon"s2 = "onion"
פלט: false
הסבר: תתי-המחרוזות באורך 4 הן onio ו-nion. כדי להרכיב את noon צריך שני n ושני o, ובכל חלון יש i במקום אחת מהן. כל האותיות של noon מופיעות ב-onion, אבל באף חלון אין את הכמויות הנכונות.

קלט: s1 = "abcd"s2 = "dcb"
פלט: false
הסבר: בכל תמורה של abcd יש 4 אותיות, וב-dcb יש רק 3, ולכן היא לא יכולה להכיל תמורה כזאת.

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

שאלת המשך

האם אפשר להחזיר כל אינדקס שבו מתחילה תמורה של s1 בתוך s2, עדיין בזמן O(m + n)?

רמזים

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

נפתחו 0 מתוך 3

פתרון

למנות את כל התמורות של s1 זה חסר טעם: ל־10 אותיות כבר יש 3,628,800 סידורים. הדרך להתמודד עם זה היא להפסיק להתחשב בסדר. תת־מחרוזת של s2 היא תמורה של s1 בדיוק כאשר אורכה זהה ל־m ויש בה אותו מספר של כל אות. לכן כל מועמד הוא חלון באותו אורך קבוע, ואפשר להחליק חלון אחד לאורך s2, ולעדכן בכל צעד את ספירות האותיות שלו: אות אחת נכנסת ואות אחת יוצאת.

ספרו כל חלון מחדש

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

האינטואיציה

הקריאה המילולית, לבנות כל תמורה של s1 ולחפש אותה, נכשלת מיד: ל־20 אותיות יש יותר מ־2 × 10^18 סידורים. במקום זאת, הפכו את השאלה. תת־מחרוזת של s2 היא תמורה של s1 כאשר יש בה בדיוק m אותיות, וכל אות מופיעה בה אותו מספר פעמים כמו ב־s1. הסדר הפנימי שלה אינו משנה.

לכן ספרו פעם אחת את האותיות של s1 בטבלה של 26 מספרים, עם אינדקס 0 עבור a ו־25 עבור z. לאחר מכן עברו על כל תת־מחרוזת של s2 באורך m, ספרו את האותיות שלה בטבלה חדשה והשוו בין שתי הטבלאות. עבור tar בתוך smartphone, החלונות הם sma, mar, art וכן הלאה, ו־art תואמת: a אחת, r אחת, t אחת.

הפתרון נכון כי הוא בודק כל מועמדת. הוא איטי כי חלונות סמוכים חולקים m-1 אותיות, ואתם סופרים מחדש את כולן. כאשר m = 15,000 ו־n = 50,000, יש 35,001 חלונות, שבכל אחד מהם 15,000 אותיות — בערך 5 × 10^8 צעדים.

אלגוריתם

אם s1 ארוך יותר מ-s2, החזר false.
ספור את האותיות של s1 בטבלה need שמכילה 26 אפסים.
עבור כל אינדקס התחלה מ-0 עד n-m, ספור את האותיות של m התווים מאותה נקודת התחלה בטבלה חדשה.
אם הטבלה הזאת שווה ל-need, החזר true.
אחרי החלון האחרון, החזר false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

הזיזו את החלון והשוו בין 26 ספירות

האינטואיציה

שני חלונות סמוכים נבדלים בשתי אותיות בלבד. המעבר מ־mar ל־art מסיר את m משמאל ומוסיף את t מימין. לכן שמור טבלה אחת עבור החלון הנוכחי ועדכן אותה בכל צעד באמצעות ‎+1 אחד ו־‎-1 אחד, במקום לספור שוב את m האותיות.

מלא את need מתוך s1 ואת window מתוך m האותיות הראשונות של s2, והשווה ביניהן. לאחר מכן, עבור כל i מ־m עד n-1, הוסף את s2[i], הסר את s2[i-m], והשווה שוב. כעת החלון הוא s2[i-m+1..i], ועדיין מכיל m אותיות.

כל צעד דורש שני עדכונים והשוואה של 26 מספרים, בלי קשר לערך של m. עבור הקלט הגדול ביותר מדובר בכ־26 × 50,000 = 1.3 × 10^6 פעולות, כלומר סיבוכיות ליניארית ביחס לאורך של s2. זה הפתרון שרוב המראיינים מצפים לו.

אלגוריתם

אם s1 ארוכה יותר מ-s2, החזר false.
ספור את התווים של s1 לתוך need ואת m האותיות הראשונות של s2 לתוך window.
אם שתי הטבלאות שוות, החזר true.
עבור כל i מ-m עד n-1: הוסף 1 עבור s2[i], החסר 1 עבור s2[i-m], והחזר true אם הטבלאות שוות.
החזר false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

הזיזו את החלון ועקבו אחר האותיות שאינן מאוזנות

האינטואיציה

השוואה של 26 מספרים בכל צעד חוזרת על עבודה, כי צעד משנה רק שניים מהם. במקום זאת, שמרו טבלה אחת balance: balance[c] הוא מספר העותקים של האות c שיש ב-s1 פחות מספר העותקים שיש בחלון. החלון הוא תמורה של s1 בדיוק כאשר כל 26 הערכים הם 0. לצד הטבלה, שמרו את unbalanced, מספר האותיות שהערך שלהן אינו 0, והשיבו true ברגע שהוא מגיע ל-0.

לניהול המעקב יש כלל אחד. לפני שמשנים את balance[c], אם ערכו 0, האות עומדת לצאת מאיזון, לכן הוסיפו 1 ל-unbalanced. אחרי השינוי, אם ערכו 0, האות הגיעה לאיזון, לכן הפחיתו 1. כניסת אות לחלון מפחיתה את הערך שלה ב-1; יציאתה מהחלון מגדילה אותו ב-1. שינוי של ערך מ-2 ל-1 אינו מפעיל אף אחת מהבדיקות, ובצדק: האות לא הייתה מאוזנת, והיא עדיין אינה מאוזנת.

עברו על tar ו-smartphone. הערכים מתחילים כך: a: 1, r: 1, t: 1, ולכן unbalanced הוא 3. s ו-m נכנסות ומעלות אותו ל-5, ואז a נכנסת ומביאה את a ל-0: 4. r נכנסת (3) בזמן ש-s יוצאת (2). t נכנסת (1) בזמן ש-m יוצאת (0), והחלון art הוא התשובה.

אפשר לבדוק אם unbalanced == 0 כבר מהאות הראשונה. כל עוד החלון מכיל פחות מ-m אותיות, סכום הערכים חיובי, ולכן לפחות אחד מהם אינו 0. בכל צעד מתבצעת כמות עבודה קבועה, לכן הסריקה כולה היא O(m + n), והטבלה מכילה תמיד 26 מספרים, כלומר נדרשים O(1) מקומות בזיכרון.

אלגוריתם

אם s1 ארוך יותר מ־s2, החזר false.
ספור את האותיות של s1 בתוך balance והגדר את unbalanced למספר האותיות שהיתרה שלהן שונה מ־0.
עבור כל אינדקס i של s2, החסר 1 מהיתרה של s2[i], הוסף 1 ל־unbalanced אם היתרה הזו הייתה 0 והחסר 1 אם היא נעשית 0.
אם i ≥ m, הוסף 1 ליתרה של s2[i-m] עם אותו עדכון מונים.
אם unbalanced הוא 0, החזר true. לאחר הלולאה, החזר false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

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

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

בדיקה שכל אות של s1 נמצאת בחלון. onio מכילה את כל האותיות של noon, ובכל זאת היא אינה תמורה שלה. השוו בין הספירות.
הסרת האות הלא נכונה. כאשר s2[i] נכנסת, האות שיוצאת היא s2[i-m], ולכן החלון הופך ל-s2[i-m+1..i]. הסרת s2[i-m+1] משאירה חלון של m-1 אותיות.
דילוג על החלון הראשון. אם משווים רק אחרי הזזת החלון, תמורה באינדקס 0 לעולם לא תימצא.
שכחה של המקרה שבו s1 ארוכה יותר מ-s2. ב-Rust, פעולת n - m עם אורכים מטיפוס unsigned גורמת לגלישה כלפי מטה, וב-Swift הטווח 0...(n - m) גורם לקריסה. החזירו קודם את false.
השוואת מערכים באמצעות == בשפה שבה ההשוואה בודקת הפניות. ב-JavaScript וב-Dart שני מערכים שונים לעולם אינם ==; ב-Java השתמשו ב-Arrays.equals.

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

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

בשימוש בחלון הזזה, הסיבוכיות היא O(m + n), כאשר m הוא האורך של s1 ו-n הוא האורך של s2. סופרים את s1 פעם אחת, ואז כל אות ב-s2 נכנסת לחלון פעם אחת ויוצאת ממנו פעם אחת. ספירה מחדש של כל חלון מההתחלה עולה O(n · m) במקום זאת.

האם תמורה במחרוזת זהה למציאת אנגרמה בתוך מחרוזת?

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

למה חלון ההזזה הוא בגודל קבוע כאן?

בכל תמורה של s1 יש בדיוק m אותיות, ולכן רק חלונות באורך m יכולים להתאים. בבעיות כמו תת־המחרוזת הארוכה ביותר ללא חזרות, החלון מתרחב ומתכווץ; כאן שני הקצוות נעים יחד, צעד אחד בכל פעם.

האם אפשר להשתמש במפת גיבוב במקום במערך של 26 מונים?

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

Python

def checkInclusion(s1, s2):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s1 = "tar"
s2 = "smartphone"

צפוי

true

Permutation in String

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

ספרו כל חלון מחדש

הזיזו את החלון והשוו בין 26 ספירות

הזיזו את החלון ועקבו אחר האותיות שאינן מאוזנות

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

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

בעיות דומות