חידה תכנותית: האם אנגרמה?

תיאור הבעיה: "אנגרמה" (שיכול אותיות) היא מילה או ביטוי שנוצר על ידי סידור מחדש של האותיות של מילה או ביטוי תוך שימוש בכל האותיות של המילה המקורית פעם אחת בדיוק.

בהינתן שתי מחרוזות `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 הוא כאורך הארוך מבין מחרוזות הקלט.

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

מילונים בשפת פייתון

חידה תכנותית: twoSum

שימוש בטכניקות שני המצביעים לפתרון בעיות תכנותיות

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים