חידה תכנותית: האם אנגרמה?
תיאור הבעיה: "אנגרמה" (שיכול אותיות) היא מילה או ביטוי שנוצר על ידי סידור מחדש של האותיות של מילה או ביטוי תוך שימוש בכל האותיות של המילה המקורית פעם אחת בדיוק.
בהינתן שתי מחרוזות `txt1` ו-`txt2`, אתה צריך לכתוב פונקציה לקביעה האם `txt2` הוא אנגרמה של `txt1`.
דוגמאות:
Input: txt1 = "apt", txt2 = "tap" Output: True Input: txt1 = "text", txt2 = "text" Output: True Input: txt1 = "race", txt2 = "car" Output: False
המשימה היא לכתוב פונקציה המקבלת שתי מחרוזות, `txt1` ו-`txt2`, כקלט ומחזירה True אם `txt2` הוא אנגרמה של `txt1`, ו-False אחרת.
פתרון ראשון לאתגר "האם אנגרמה"
הפונקציה is_anagram() מקבלת שתי מחרוזות כקלטים:
def is_anagram(txt1, txt2):
pass
הפונקציה ראשית בודקת אם אורך הקלטים שונה כי הגדרת האנגרמה מחייבת מחרוזות שוות אורך:
# Check lengths as valid anagrams must have the same size
if len(txt1) != len(txt2):
return False
נשתמש במילון של פייתוןhashmap למניית מספר התווים מכל סוג בקלט `txt1`:
# Count characters in `txt1`
for c in txt1:
# If the character is not in the hashmap, add it with a count of 1
if c not in char_counter:
char_counter[c] = 1
# If the character is already in the hashmap, increment its count
else:
char_counter[c] += 1
לצורך השוואה עם המחרוזת השנייה, `text2`, נעבור על כל אחד מהתווים של המחרוזת השנייה ועבור כל אחד מהם נבדוק האם התו קיים במילון:
- במידה והתו אינו קיים, זו אינה אנגרמה כי המחרוזת השנייה מכילה תו שלא קיים בראשונה. לפיכך, נחזיר False.
- במידה והתו קיים, נפחית 1 ממונה התו במילון.
# To compare with `txt2`
# check if each character in `txt2` is in the hashmap
# if it doesn't return False. If it is reduce by 1 the
# the count associated with the character
for c in txt2:
# If the character is not in the hashmap, it's not an anagram, return False
if c not in char_counter:
return False
# If the character is in the hashmap, decrement its count
else:
char_counter[c] -= 1
בבדיקה האחרונה, נעבור על המילון. במידה ואחד ממוני התווים מכיל ערך השונה מ-0 אז זו אינה אנגרמה. לפיכך, נחזיר False.
# Check the count for each character in the hashmap.
# If any character's count is not 0, it's not an anagram, return False
for c in char_counter.keys():
if char_counter[c] != 0:
return False
במידה ועברנו את כל הבדיקות לעיל, לא נשאר דבר מלבד להחזיר True כי המחרוזות הם אנגרמות.
עכשיו הכל ביחד:
def is_anagram(txt1, txt2):
# Check lengths as valid anagrams must have the same size
if len(txt1) != len(txt2):
return False
# Hashmap to count the characters
char_counter = {}
# Count characters in `txt1`
for c in txt1:
# If the character is not in the hashmap, add it with a count of 1
if c not in char_counter:
char_counter[c] = 1
# If the character is already in the hashmap, increment its count
else:
char_counter[c] += 1
# To compare with `txt2`
# check if each character in `txt2` is in the hashmap
# if it doesn't return False. If it is reduce by 1 the
# the count associated with the character
for c in txt2:
# If the character is not in the hashmap, it's not an anagram, return False
if c not in char_counter:
return False
# If the character is in the hashmap, decrement its count
else:
char_counter[c] -= 1
# Check the count for each character in the hashmap.
# If any character's count is not 0, it's not an anagram, return False
for c in char_counter.keys():
if char_counter[c] != 0:
return False
# If all characters have matching counts, it's an anagram, return True
return True
נבדוק את הפונקציה is_anagram():
# Test cases
print(is_anagram("txt","txt")) # True
print(is_anagram("text","txt")) # False
print(is_anagram("txt","text")) # False
print(is_anagram("txet","txet")) # True
print(is_anagram("rat","pat")) # False
print(is_anagram("race","car")) # False
- מהגדרת האנגרמה אפשר להבין שאין צורך להתחשב ברווחים בין מילים אז אפשר להכניס גם את זה לקוד לעיל.
ניתוח ביצועים
חשוב שהפונקציה תהיה יעילה ולא רק תעבוד. הפסקאות הבאות משתמשות בנוטציה של big-O עליה ניתן לקרוא במדריך big-O ביטוי ליעילות הקוד.
סיבוכיות זמן: הפונקציה מורכבת משלוש לולאות. הלולאה הראשונה עוברת על התווים במחרוזת הקלט `txt1`, הלולאה השנייה עוברת על התווים במחרוזת הקלט `txt2`, והלולאה השלישית עוברת על המפתחות במילון `char_counter`. כל אחת מהלולאות יכולה לרוץ לכל היותר N פעמים, כאשר N הוא מספר התווים במחרוזות הקלט. לכן, סיבוכיות הזמן של הפונקציה היא O(N), לינארית ביחס לגודל הקלט.
סיבוכיות מקום: הגורם העיקרי המשפיע על סיבוכיות המקום הוא המילון `char_counter`. במקרה הגרוע, למילון זה עשוי להיות מפתח עבור כל תו ייחודי במחרוזות הקלט שאורכה N תווים. לכן, סיבוכיות המקום היא O(N), כי היא גדלה באופן ליניארי עם גודל הקלט.
פתרון שני קומפקטי במיוחד
את כל מה שהפונקציה is_anagram() עושה אפשר לעשות בשורה אחת:
def is_anagram(txt1, txt2):
return sorted(txt1) == sorted(txt2)
הפונקציה ממיינת את מחרוזות הקלט באמצעות המתודה הפייתונית sorted() דבר מבטיח ששתי המחרוזות יהיו בסדר אלפביתי, ללא קשר לסדר שבו האותיות מופיעות במחרוזות המקוריות. לאחר מיון המחרוזות, הפונקציה משווה אותן באמצעות האופרטור ==. אם הן זהות, אז הן אנגרמות, והפונקציה מחזירה True. אחרת, הפונקציה מחזירה False.
סיבוכיות זמן:
- המתודה sorted() משתמשת באלגוריתם Timsort המשלב insertion sort ו-mergesort ומתאפיין בסיבוכיות זמן הקרובה ללינאריתמית O(N*logN). אומנם אנחנו מריצים את המתודה פעמיים אבל החלק הלינאריתמי הוא התורם העיקרי אז נפשט לסיבוכיות זמן O(N*logN).
- לאחר מיון שני הרצפים, הפונקציה משווה בין שני הרצפים הממוינים, בתהליך שיש לו סיבוכיות זמן O(N). לפיכך, הסיבוכיות הזמן הכוללת היא O(N*logN) + O(N), אותה נפשט ל-O(N*logN).
סיבוכיות מקום:
- המתודה sorted() יוצרת רשימות חדשות באורך N לאחסון הגרסאות הממוינות של הקלטים. סיבוכיות המקום הנדרש למיון הוא לפיכך O(N), כאשר N הוא אורך רצף הקלט.
לסיכום, סיבוכיות הזמן של פונקציית is_anagram() היא O(N*log(N)), וסיבוכיות המקום היא O(N), כאשר אורכו של N הוא כאורך הארוך מבין מחרוזות הקלט.
מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך
שימוש בטכניקות שני המצביעים לפתרון בעיות תכנותיות
לכל המדריכים בסדרה ללימוד פייתון
אהבתם? לא אהבתם? דרגו!
0 הצבעות, ממוצע 0 מתוך 5 כוכבים
המדריכים באתר עוסקים בנושאי תכנות ופיתוח אישי. הקוד שמוצג משמש להדגמה ולצרכי לימוד. התוכן והקוד המוצגים באתר נבדקו בקפידה ונמצאו תקינים. אבל ייתכן ששימוש במערכות שונות, דוגמת דפדפן או מערכת הפעלה שונה ולאור השינויים הטכנולוגיים התכופים בעולם שבו אנו חיים יגרום לתוצאות שונות מהמצופה. בכל מקרה, אין בעל האתר נושא באחריות לכל שיבוש או שימוש לא אחראי בתכנים הלימודיים באתר.
למרות האמור לעיל, ומתוך רצון טוב, אם נתקלת בקשיים ביישום הקוד באתר מפאת מה שנראה לך כשגיאה או כחוסר עקביות נא להשאיר תגובה עם פירוט הבעיה באזור התגובות בתחתית המדריכים. זה יכול לעזור למשתמשים אחרים שנתקלו באותה בעיה ואם אני רואה שהבעיה עקרונית אני עשוי לערוך התאמה במדריך או להסיר אותו כדי להימנע מהטעיית הציבור.
שימו לב! הסקריפטים במדריכים מיועדים למטרות לימוד בלבד. כשאתם עובדים על הפרויקטים שלכם אתם צריכים להשתמש בספריות וסביבות פיתוח מוכחות, מהירות ובטוחות.
המשתמש באתר צריך להיות מודע לכך שאם וכאשר הוא מפתח קוד בשביל פרויקט הוא חייב לשים לב ולהשתמש בסביבת הפיתוח המתאימה ביותר, הבטוחה ביותר, היעילה ביותר וכמובן שהוא צריך לבדוק את הקוד בהיבטים של יעילות ואבטחה. מי אמר שלהיות מפתח זו עבודה קלה ?
השימוש שלך באתר מהווה ראייה להסכמתך עם הכללים והתקנות שנוסחו בהסכם תנאי השימוש.