בעיה זו דומה מאד לשאלה האם סטרינג מסוים הוא פלינדרום. בבעיה זו נקבל שתי מילים ונצטרך להשיב האם שתיהן עונות להגדרת האנגרמה. שתי מילים יחשבו אנגרמה אחת של השניה אם הם מורכבים מאותם אותיות - לא חשוב הסדר.
למשל המילים: was / saw או note / tone הן אנגרמה.
דרישות:
- יעילות זמן: n
- יעילות מקום: n
הפתרון לבעיה זו הוא די פשוט אך דורש מעט מחשבה מוקדמת.
אנחנו מבינים שמיון לא יעזור כיוון שגם מיון יעיל יוביל אותנו ליעילות של n log n.
המפתח נעוץ בספירת כמות האותיות במילה - במידה וכמות מופעי האותיות במילים שוות - הן בהגדרה אנגרמה.
הדרך הפשוטה לבצע זאת היא באמצעות שימוש ב-Hash Table כיוון שקל לעדכן את הפריטים בטבלה ביעילות של 1.
תחילה נעבור על המילה הראשונה כאשר ה-key בטבלה תהיה האות וה-value שלה תהיה כמות המופעים שלה. לאחר מכן נעבור על המילה השניה באותה תצורה ולבסוף נשווה בין ערכי הטבלאות.
אין תגובות:
הוסף רשומת תגובה