Reverse a String

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

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

Q: איך הופכים מחרוזת בלי להשתמש בפונקציית היפוך מובנית?

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

Q: האם אפשר להפוך מחרוזת במקום?

רק כאשר התווים נמצאים במאגר שניתן לשינוי, כמו מערך char ב־C, ב־Java או ב־C#, רשימה ב־Python או std::string ב־C++. מחרוזות ב־Java, ב־Python, ב־JavaScript ובשפות רבות אחרות אינן ניתנות לשינוי, ולכן מעתיקים אותן למערך, מחליפים את התווים בתוכו ובונים מחרוזת חדשה. שלב ההחלפה עצמו מתבצע במקום בכל מקרה.

Q: למה לולאת שני המצביעים נעצרת באמצע?

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

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

+10

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

פונקציה

reverseString(s: string) → string

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

אילוצים

1 ≤ s.length ≤ 10⁴
s מכיל רק אותיות באנגלית (a עד z, A עד Z) וספרות (0 עד 9).

דוגמאות

קלט: s = "Coddy2026"
פלט: "6202yddoC"
הסבר: קראו את Coddy2026 מהתו האחרון שלו ועד לראשון: 6, 2, 0, 2, אחר כך y, d, d, o ולבסוף האות הגדולה C.

קלט: s = "noon"
פלט: "noon"
הסבר: noon היא פלינדרום, ולכן ההיפוך שלה הוא אותה מילה. ה־nים החיצוניים מחליפים מקומות, ואז שני ה־oים עושים זאת.

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

שאלת המשך

איך תהפוך את סדר המילים במשפט, כך ש-hello big world יהפוך ל-world big hello, תוך שמירה על סדר האותיות בכל מילה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

העתק את התווים מהסוף

האינטואיציה

ההיפוך של s מתחיל בתו האחרון של s, ממשיך בזה שלפני האחרון ומסתיים בראשון. לכן עוברים עם אינדקס מ־n-1 עד 0 ומוסיפים כל תו לתשובה כשמגיעים אליו. עבור Coddy2026 מוסיפים את 6, את 2, את 0, את 2, את y וכן הלאה, כך שמתקבלת המחרוזת 6202yddoC.

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

חשוב לשים לב לאופן ההוספה. הוספת תו אחד למחרוזת בלתי ניתנת לשינוי באמצעות + מעתיקה את המחרוזת כולה בכל פעם, ועבור n = 10^4 מדובר בכ־5 × 10^7 העתקות תווים. אספו את התווים ברשימה או בבונה מחרוזות, וחברו אותם פעם אחת בסוף.

אלגוריתם

צרו רשימה ריקה או בונה מחרוזות עבור התשובה.
עברו בלולאה על i מ־n-1 ועד 0.
הוסיפו את s[i] לתשובה.
חברו את התשובה למחרוזת והחזירו אותה.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

החליפו משני הקצוות באמצעות שני מצביעים

האינטואיציה

היפוך מחליף בין זוגות של תווים, מבחוץ פנימה. הראשון והאחרון מחליפים מקומות, אחר כך השני והאחד שלפני האחרון, וכן הלאה לכיוון האמצע. הצב מצביע left באינדקס 0 ומצביע right באינדקס n-1, החלף בין שני התווים והזז את שני המצביעים צעד אחד פנימה.

עצור כשהמצביעים נפגשים או חוצים זה את זה. במחרוזת noon המצביעים מתחילים באינדקסים 0 ו-3, ואז נעים אל 1 ו-2, ולאחר מכן חוצים זה את זה, אחרי שתי החלפות. באורך אי-זוגי, כמו xYz, הם נפגשים בתו האמצעי, שכבר נמצא במקומו הסופי ולכן לעולם לא נוגעים בו. כל החלפה מציבה שני תווים במקומותיהם הסופיים, ולכן n / 2 החלפות משלימות את המשימה.

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

אלגוריתם

העתיקו את s למערך של תווים.
הגדירו left = 0 ואת right = n-1.
כל עוד left < right, החליפו בין התווים במיקומים left ו-right, ואז הוסיפו 1 ל-left והחסירו 1 מ-right.
הפכו את המערך בחזרה למחרוזת והחזירו אותה.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

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

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

הרצה של left עד n-1. אחרי שחוצים את האמצע, כל זוג מוחלף פעם שנייה והמחרוזת חוזרת למצבה המקורי. עצור ב-left < right.
התחלת הלולאה לאחור ב-n במקום ב-n-1, כך שקוראים מיקום אחד מעבר לסוף. ב-Lua וב-R האינדקסים נעים מ-1 עד n במקום זאת.
בניית התשובה באמצעות result = result + ch במחרוזת בלתי ניתנת לשינוי. בכל צעד מועתק כל מה שנבנה עד כה, וכך משימה ליניארית הופכת למשימה ריבועית בקלטים ארוכים.
שכחת תו הסיום '\0' ב-C. חסר בית אחד במאגר בגודל n; הקצה n + 1.
החלפה ללא משתנה זמני: אחרי chars[left] = chars[right] התו הישן שבצד שמאל אובד, אלא אם השפה שלך מחליפה את שני הערכים בבת אחת.

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

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

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

איך הופכים מחרוזת בלי להשתמש בפונקציית היפוך מובנית?

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

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

רק כאשר התווים נמצאים במאגר שניתן לשינוי, כמו מערך char ב־C, ב־Java או ב־C#, רשימה ב־Python או std::string ב־C++. מחרוזות ב־Java, ב־Python, ב־JavaScript ובשפות רבות אחרות אינן ניתנות לשינוי, ולכן מעתיקים אותן למערך, מחליפים את התווים בתוכו ובונים מחרוזת חדשה. שלב ההחלפה עצמו מתבצע במקום בכל מקרה.

למה לולאת שני המצביעים נעצרת באמצע?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

s = "Coddy2026"

צפוי

"6202yddoC"