221
0

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

221
זמן קריאה: 2 דקות

הבעיה: כתוב פונקציה, אשר בהינתן מחרוזת S, החזר מחרוזת לאחר ביצוע פעולת reverse על מחרוזת הקלט ברמת המחרוזת כולה (ולא המילה).

לדוגמא:

בהינתן המחרוזת

"the sky is blue"

הפלט של השגרה אמור להיות:

"blue is sky the"

הערות ודגשים:

  1. מילה מוגדרת כרצף תווים ללא רווח בתוכו.
  2. אין להשאיר רווחים בתחילת המחרוזת המוחזרת, גם אם הם היו קיימים במחרוזת הקלט.
  3. במידה ובמחרוזת הקלט ישנם כמה רווחים בין זוג מילים, יש להשאיר רווח יחיד במחרוזת החוזרת.

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

  1. בהינתן קלט, פרק אותו למילים בודדות בצורה הבא:

    1.1 סרוק את המחרוזת מתחילתה, במידה ונתקלת בתו, סמן את מיקום התו (index).
    1.2 המשך עד שתתקל בתו שמייצג רווח.
    1.3 בנה מילה מהאינדקס ששמרת עד אינדקס אחד לפני הרווח.
    1.4 אחסן את המילה ברשימה/מערך ע”י הכנסת המילה החדשה למיקום הראשון ברשימה – דבר זה יבטיח לנו שסדר המילים יהיה הפוך.

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

3. החזר את המחרוזת

גרסת Python

				
					def solve(A):
    words_container= A.split()[::-1]
    return " ".join(words_container)
				
			

סיבוכיות:

סיבוכיות זמן: O(n^2)

סיבוכיות מקום: O(n)

פתרון נוסף, חסכוני יותר:

				
					def solve(A):
        words = A.split()
        words_container =[]
        for word in words:
            words_container.insert(0, word)
        return " ".join(words_container)
				
			

סיבוכיות:

סיבוכיות זמן: O(n)

סיבוכיות מקום: O(n)

גרסת C#

				
					public string ReverseWords(string sentence)
    {
        string[] words = sentence.Split(' ');
        Array.Reverse(words);
        return string.Join(" ", words);
    }
				
			

בונוס פייתוני

שימו לב שהשימוש במתודת split נעשה ע”י ה delimiter הדיפולטיבי ולא ע”י ‘ ‘.
האם הפתרון עדיין יעבוד אם נעביר את ‘ ‘ בתור delimiter? תכתבו לי בתגובות מה דעתכם.

עומרי נעים
WRITEN BY

עומרי נעים

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *