String Compression

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

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

Q: האם המחרוזת הדחוסה יכולה להיות ארוכה יותר מהמחרוזת המקורית?

לא בגרסה הזאת. אות בודדת נשארת תו אחד, ורצף של k ≥ 2 אותיות הופך לאות אחת בתוספת הספרות של k , ולעולם לא ליותר מ־ k תווים. שיטה שכותבת ספירה אחרי כל אות, כמו a1b1 , עלולה להכפיל את האורך.

קלשני מצביעים מערכים ומחרוזות

+10

נתונה לך מחרוזת s של אותיות באנגלית. דחוס אותה: החלף כל רצף של שתי אותיות זהות או יותר ברצף באות הזאת ואחריה אורך הרצף, והשאר אות שעומדת לבדה כפי שהיא. לכן aabccc הופכת ל־a2bc3. החזר את המחרוזת הדחוסה.

אותיות גדולות וקטנות נחשבות לאותיות שונות: aA הם שני רצפים באורך 1.

פונקציה

compress(s: string) → string

sstring: המחרוזת לדחיסה, אותיות באנגלית בלבד
מחזירהstring: המחרוזת הדחוסה, שבה כל רצף נכתב כאות שלו ואחריה אורכו, כאשר האורך גדול מ־1

אילוצים

1 ≤ s.length ≤ 2 × 10⁴
s מכילה רק אותיות באנגלית, a עד z ו-A עד Z.
אורך רצף נכתב בשיטה העשרונית ויכול להכיל כמה ספרות.

דוגמאות

קלט: s = "aabccc"
פלט: "a2bc3"
הסבר: הרצפים הם aa, b ו־ccc. הם הופכים ל־a2, b (אות בודדת לא מקבלת ספירה) ול־c3.

קלט: s = "abbbbbbbbbbbb"
פלט: "ab12"
הסבר: אחד a, ואז שנים-עשר b. האורך 12 נכתב כשתי התווים 1 ו-2, ולכן התוצאה היא ab12.

קלט: s = "zzZZZ"
פלט: "z2Z3"
הסבר: האות הקטנה z והאות הגדולה Z הן אותיות שונות, לכן זהו רצף של שתיים ואחריו רצף של שלוש: z2Z3.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

אסוף את הרצפים, ואז כתוב אותם

האינטואיציה

תחילה תעדו את הרצפים כזוגות של אות ואורך: עבור aabccc, (a, 2), (b, 1), (c, 3). כל אות מאריכה את הרצף האחרון או פותחת רצף חדש. לאחר מכן כתבו את האות של כל רצף, ואחריה את אורכו אם הוא גדול מ-1.

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

אלגוריתם

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

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

שני מצביעים בכל רצף

האינטואיציה

השאר את i באות הראשונה של הרצף הנוכחי והזז את j קדימה כל עוד s[j] שווה ל־s[i]. כשהתנועה של j נעצרת, באות אחרת או בסוף, אורך הרצף הוא j-i. כתוב אותו וקבע i = j. במחרוזת abbbbbbbbbbbb, התנועה של j נעצרת תחילה ב־1, מה שנותן a, ואז ב־13, מה שנותן b12.

אין צורך במקרה מיוחד עבור הרצף האחרון, כי הלולאה הפנימית נעצרת בסוף המחרוזת. j מתקדם רק קדימה, לכן זמן הריצה הוא O(n), ובנוסף לתוצאה נשמרים שני אינדקסים. גרסאות R ו־Swift מפצלות תחילה את s למערך תווים, ולכן הן משתמשות ב־O(n) של מקום נוסף.

אלגוריתם

הגדר את i = 0.
כל עוד i נמצא בתוך המחרוזת, הגדר את j = i והזז את j קדימה כל עוד הוא בתוך המחרוזת ו-s[j] שווה ל-s[i].
כתוב את s[i]; אם j-i גדול מ-1, כתוב אותו כטקסט עשרוני.
הגדר את i = j וחזור על הפעולה.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

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

כתיבת רצף רק כשנתקלים באות שונה. אחרי ה-ccc האחרון של aabccc לא מופיע דבר, ולכן מחזירים a2b.
כתיבת הספירה כתו אחד, למשל '0' + count. זה נכשל ב-10: נדרשים שני התווים 12 עבור שתים-עשרה אותיות b.
כתיבת 1 אחרי אות שמופיעה פעם אחת. b נשארת b, ולא b1.
התעלמות מהבדלי אותיות גדולות וקטנות. zzZZZ היא z2Z3, ולא z5.
הגדלת מחרוזת בלתי משתנה באמצעות +, כמו ב-Java או ב-C#. כל + מעתיק את התוצאה עד לאותו שלב, מה שהופך את הלולאה ל-O(n²); יש להשתמש בבונה מחרוזות.

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

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

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

האם המחרוזת הדחוסה יכולה להיות ארוכה יותר מהמחרוזת המקורית?

לא בגרסה הזאת. אות בודדת נשארת תו אחד, ורצף של k ≥ 2 אותיות הופך לאות אחת בתוספת הספרות של k, ולעולם לא ליותר מ־k תווים. שיטה שכותבת ספירה אחרי כל אות, כמו a1b1, עלולה להכפיל את האורך.

איך דוחסים מחרוזת במקום?

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

def compress(s):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

s = "aabccc"

הפלט הצפוי

"a2bc3"