Reverse Words in a String

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

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

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

+10

ניתנת לך מחרוזת s המורכבת ממילים ומרווחים. מילה היא רצף של אותיות וספרות ללא רווח בתוכה. מילים יכולות להיות מופרדות ביותר מרווח אחד, ו-s יכולה להתחיל או להסתיים ברווחים.

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

פונקציה

reverseWords(s: string) → string

sstring: אותיות, ספרות ורווחים שמכילים לפחות מילה אחת
מחזירהstring: המילים של s בסדר הפוך, מופרדות ברווח יחיד

אילוצים

1 ≤ s.length ≤ 10⁴
s מכיל רק אותיות באנגלית, ספרות ורווחים.
s מכיל לפחות מילה אחת.

דוגמאות

קלט: s = "Coddy runs in 15 languages"
פלט: "languages 15 in runs Coddy"
הסבר: המילים הן Coddy, runs, in, 15 ו-languages. בקריאה מהסוף להתחלה הן יוצרות את languages 15 in runs Coddy; 15 נחשב למילה כי מילים יכולות להכיל ספרות.

קלט: s = " practice makes progress "
פלט: "progress makes practice"
הסבר: הרווחים בשני הקצוות מוסרים, והרצפים של שניים ושלושה רווחים בין המילים מצטמצמים לרווח אחד. שלוש המילים יוצאות בסדר הפוך, מהאחרונה לראשונה: progress makes practice.

קלט: s = " single "
פלט: "single"
הסבר: רשימה של מילה אחת נקראת אותו דבר גם מהסוף להתחלה. רק הרווחים שסביבה נעלמים, ולכן התשובה היא single.

שאלת המשך

האם תוכל להפוך את סדר המילים, אבל לשמור על הרווחים של s: אותם רצפים של רווחים, באותם אורכים ובאותו סדר?

פתרון

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

פצלו למילים וחברו אותן בסדר הפוך

האינטואיציה

פצלו את s למילים שמרכיבות אותו, הפכו את סדר הרשימה וחברו אותה באמצעות רווחים בודדים. צריך להיזהר בפיצול: פיצול של " practice makes progress " בכל רווח יחיד יוצר שישה חלקים ריקים מסביב לשלוש המילים. הסירו את החלקים הריקים, והרשימה היא practice, makes, progress.

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

אלגוריתם

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

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

הפוך את המחרוזת כולה, ואז כל מילה

האינטואיציה

היפוך של המחרוזת כולה מסדר את המילים בסדר הנכון, אבל מאיית כל אחת מהן לאחור: Coddy runs in 15 languages הופכת ל־segaugnal 51 ni snur yddoC. היפוך של כל מילה בנפרד נותן אז את languages 15 in runs Coddy.

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

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

אלגוריתם

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

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

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

פיצול לפי רווח יחיד ושמירה על כל חלק. "a b" מתפצל ל־a, לחלק ריק ול־b, והחיבור מחזיר שני רווחים: "b a".
הנחה שפיצול משמיט את החלקים שבקצוות. split(" ") של Java משמיט חלקים ריקים בסוף, אבל שומר אותם בתחילת המחרוזת, לכן " a b" עדיין משאיר אחד.
הוספת רווח אחרי כל מילה, כולל האחרונה, כך שהתשובה מסתיימת ברווח. הוסיפו רווח לפני כל מילה מלבד הראשונה.
ביצוע היפוך אחד בלבד בגרסה שמשנה את המערך במקום. היפוך של המילים בלבד נותן yddoC snur ni 51 segaugnal.
ב־PHP וב־R, קלט שמורכב כולו מספרות, כגון 2026, עשוי להתקבל כמספר. הפכו אותו למחרוזת לפני הפיצול.

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

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

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

איך מטפלים ברווחים מרובים בין מילים?

התייחסו למילה כרצף של תווים שאינם רווחים, ולעולם אל תעתיקו רווחים מהקלט. פיצול ללא מפריד ב-Python וב-Ruby, strings.Fields ב-Go ו-split_whitespace ב-Rust כבר מדלגים על כל רצף של רווחים ועל הרווחים בשני הקצוות; במקומות אחרים, הסירו את החלקים הריקים. לאחר מכן כתבו רווח אחד בין המילים.

האם אפשר להפוך את סדר המילים בלי פונקציית פיצול?

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

s = "Coddy runs in 15 languages"

הפלט הצפוי

"languages 15 in runs Coddy"