הבעיה: כתוב פונקציה, אשר בהינתן מחרוזת S, החזר מחרוזת לאחר ביצוע פעולת reverse על מחרוזת הקלט ברמת המחרוזת כולה (ולא המילה).
לדוגמא:
בהינתן המחרוזת
"the sky is blue"הפלט של השגרה אמור להיות:
"blue is sky the"הערות ודגשים:
- מילה מוגדרת כרצף תווים ללא רווח בתוכו.
- אין להשאיר רווחים בתחילת המחרוזת המוחזרת, גם אם הם היו קיימים במחרוזת הקלט.
- במידה ובמחרוזת הקלט ישנם כמה רווחים בין זוג מילים, יש להשאיר רווח יחיד במחרוזת החוזרת.
כמו כל בעיה שניתנת לנו, גם במקרה הזה ישנן המון דרכים לפתור אותה.
האלגוריתם אותו נבחר לממש יהיה די נאיבי:
- בהינתן קלט, פרק אותו למילים בודדות בצורה הבא:
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? תכתבו לי בתגובות מה דעתכם.