בדוק אם שני מיתרים הם אנגרמות ב- Java
1. סקירה כללית
על פי ויקיפדיה, אנגרמה היא מילה או ביטוי שנוצרו על ידי סידור מחדש של האותיות של מילה או ביטוי אחר.
אנו יכולים להכליל זאת בעיבוד מחרוזות באומרנו זאת אנגרמה של מחרוזת היא מחרוזת אחרת עם אותה כמות בדיוק של כל תו, בכל סדר.
במדריך זה, נבחן איתור אנגרמות מחרוזות שלמות בהן הכמות של כל תו חייבת להיות שווה, כולל תווים שאינם אלפא כגון רווחים וספרות. לדוגמה, "!דל במלח!" ו "ינשופים-לט !!" ייחשבו לאנגרמות מכיוון שהם מכילים בדיוק אותן תווים.
2. פיתרון
בואו נשווה בין כמה פתרונות שיכולים להחליט אם שני מחרוזות הן אנגרמות. כל פיתרון יבדוק כבר בהתחלה אם לשני המחרוזות יש מספר זהה של תווים. זוהי דרך מהירה לצאת מוקדם מאז תשומות באורכים שונים לא יכולות להיות אנגרמות.
לכל פתרון אפשרי, בואו נסתכל על מורכבות היישום עבורנו כמפתחים. נבחן גם את מורכבות הזמן של המעבד, תוך שימוש בסימון O גדול.
3. בדוק לפי מיון
אנו יכולים לסדר מחדש את הדמויות של כל מחרוזת על ידי מיון הדמויות שלהן, שייצרו שני מערכי תווים מנורמלים.
אם שני מיתרים הם אנגרמות, הצורות המנורמליות שלהם צריכות להיות זהות.
ב- Java נוכל להמיר תחילה את שני המיתרים ל- לְהַשְׁחִיר[] מערכים. אז נוכל למיין את שני המערכים האלה ולבדוק אם קיימת שוויון:
בוליאני isAnagramSort (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } char [] a1 = string1.toCharArray (); char [] a2 = string2.toCharArray (); Arrays.sort (a1); Arrays.sort (a2); Arrays.equals להחזיר (a1, a2); } קל להבין וליישם פתרון זה. עם זאת, זמן הריצה הכללי של אלגוריתם זה הוא O (n יומן n) כי מיון מערך של נ תווים לוקח O (n יומן n) זְמַן.
כדי שהאלגוריתם יתפקד, עליו ליצור עותק משני מיתרי הקלט כמערכי תווים, תוך שימוש במעט זיכרון נוסף.
4. בדוק לפי ספירה
אסטרטגיה חלופית היא לספור את מספר המופעים של כל דמות בתשומות שלנו. אם ההיסטוגרמות הללו שוות בין הקלטים, המחרוזות הן אנגרמות.
כדי לחסוך מעט זיכרון, בואו נבנה רק היסטוגרמה אחת. נגדיל את הספירות עבור כל תו במחרוזת הראשונה, ונקטין את הספירה עבור כל תו בשנייה. אם שני המיתרים הם אנגרמות, התוצאה תהיה שהכל יתאזן ל -0.
ההיסטוגרמה זקוקה לטבלת ספירות בגודל קבוע עם גודל המוגדר על ידי גודל קבוצת התווים. לדוגמא, אם אנו משתמשים בתא אחד בלבד לאחסון כל תו, נוכל להשתמש בגודל מערך ספירה של 256 כדי לספור את המופע של כל תו:
פרטי סטטי פרטי CHARACTER_RANGE = 256; ציבור בוליאני isAnagramCounting (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } int count [] = int int [CHARACTER_RANGE]; עבור (int i = 0; i <string1.length (); i ++) {count [string1.charAt (i)] ++; ספירה [string2.charAt (i)] -; } עבור (int i = 0; i <CHARACTER_RANGE; i ++) {if (count [i]! = 0) {return false; }} להחזיר אמת; }פתרון זה מהיר יותר עם מורכבות הזמן של עַל). עם זאת, הוא זקוק למרחב נוסף עבור מערך הספירה. ב- 256 מספרים שלמים, ל- ASCII זה לא נורא.
עם זאת, אם אנחנו צריכים להגדיל CHARACTER_RANGE כדי לתמוך בערכות תווים מרובות בתים כגון UTF-8, הדבר יהפוך רעב מאוד לזיכרון. לכן, זה ממש מעשי רק כאשר מספר התווים האפשריים נמצא בטווח קטן.
מנקודת מבט של פיתוח, פתרון זה מכיל יותר קוד לתחזוקה ומשתמש פחות בפונקציות ספריית Java.
5. בדוק עם MultiSet
אנו יכולים לפשט את תהליך הספירה והשוואה באמצעות MultiSet. MultiSet הוא אוסף התומך בשוויון בלתי תלוי בסדר עם אלמנטים כפולים. לדוגמא, המולטי סטים {a, a, b} ו- {a, b, a} שווים.
להשתמש מולטי סטראשית עלינו להוסיף את התלות בגויאבה לפרויקט שלנו pom.xml קוֹבֶץ:
com.google.guava גויאבה 28.1-jre אנו להמיר כל אחד ממחרוזות הקלט שלנו ל- a MultiSet של דמויות. ואז נבדוק אם הם שווים:
בוליאני isAnagramMultiset (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } Multiset multiset1 = HashMultiset.create (); Multiset multiset2 = HashMultiset.create (); עבור (int i = 0; i <string1.length (); i ++) {multiset1.add (string1.charAt (i)); multiset2.add (string2.charAt (i)); } להחזיר multiset1.equals (multiset2); } אלגוריתם זה פותר את הבעיה ב עַל) זמן מבלי להצהיר על מערך ספירה גדול.
זה דומה לפתרון הספירה הקודם. עם זאת, במקום להשתמש בטבלה בגודל קבוע כדי לספור, אנו מנצלים את MutlitSet בכיתה כדי לדמות טבלה בגודל משתנה, עם ספירה לכל תו.
הקוד לפתרון זה עושה שימוש רב יותר ביכולות הספרייה ברמה גבוהה מאשר בפתרון הספירה שלנו.
6. אנגרמה מבוססת אותיות
הדוגמאות עד כה אינן דבקות בהגדרה הלשונית של אנגרמה. הסיבה לכך היא שהם רואים בתווי פיסוק חלק מהאנגרמה, והם תלויי אותיות רישיות.
בואו נתאים את האלגוריתמים כדי לאפשר אנגרמה מבוססת אות. בואו ניקח בחשבון את הסידור מחדש של אותיות שאינן רגישות לאותיות רישיות, ללא קשר לתווים אחרים כמו רווחים לבנים ופיסוק. לדוגמה, "נקודה עשרונית" ו "אני נקודה במקום." יהיו אנגרמות זו לזו.
כדי לפתור בעיה זו, ראשית נוכל לעבד מראש את שני מחרוזות הקלט כדי לסנן תווים לא רצויים ולהמיר אותיות באותיות קטנות. אז נוכל להשתמש באחד מהפתרונות שלעיל (נניח, ה- MultiSet פתרון) כדי לבדוק אנגרמות בחוטים המעובדים:
עיבוד מקדים של מחרוזת (מקור מחרוזת) {return source.replaceAll ("[^ a-zA-Z]", "") .toLowerCase (); } בוליאני isLetterBasedAnagramMultiset (String string1, String string2) {return isAnagramMultiset (preprocess (string1), preprocess (string2)); }גישה זו יכולה להיות דרך כללית לפתור את כל הגרסאות לבעיות האנגרמה. לדוגמא, אם אנו רוצים לכלול גם ספרות, עלינו רק להתאים את פילטר העיבוד המקדים.
7. מסקנה
במאמר זה בדקנו שלושה אלגוריתמים לבדיקה אם מחרוזת נתונה היא אנגרמה של תו אחר, אופי לדמות. עבור כל פיתרון דנו בפשרות בין המהירות, הקריאה וגודל הזיכרון הנדרש.
בדקנו גם כיצד להתאים את האלגוריתמים לבדיקת אנגרמות במובן הלשוני המסורתי יותר. השגנו זאת על ידי עיבוד מקדים של התשומות לאותיות קטנות.
כמו תמיד, קוד המקור של המאמר זמין באתר GitHub.
