מצא מיתרים שהם פליינדרומים בג'אווה
1. סקירה כללית
במדריך מהיר זה, נעבור גישות שונות ל מציאת כל המצעים בתוך מחרוזת נתונה שהם פלינדרומים. נציין גם את מורכבות הזמן של כל גישה.
2. גישת כוח הברוט
בגישה זו, פשוט נחזור על מחרוזת הקלט כדי למצוא את כל המצעים. במקביל, נבדוק האם המצע הוא פלינדרום או לא:
ציבורי הגדר findAllPalindromesUsingBruteForceApproach (קלט מחרוזת) {Set palindromes = new HashSet (); עבור (int i = 0; i <input.length (); i ++) {for (int j = i + 1; j <= input.length (); j ++) {if (isPalindrome (input.substring (i, j ))) {palindromes.add (input.substring (i, j)); }}} להחזיר palindromes; }בדוגמה שלעיל, אנו פשוט משווים את המצע לחלקו ההפוך כדי לראות אם מדובר בפלינדרום:
פרטית בוליאנית isPalindrome (קלט מחרוזת) {StringBuilder רגיל = חדש StringBuilder (קלט); StringBuilder הפוך = plain.reverse (); return (reverse.toString ()). שווה (קלט); }כמובן, אנו יכולים לבחור בקלות מכמה גישות אחרות.
מורכבות הזמן של גישה זו היא O (n ^ 3). אמנם זה עשוי להיות מקובל על מחרוזות קלט קטנות, אך נצטרך גישה יעילה יותר אם אנו מחפשים פלינדרומים בכמויות גדולות של טקסט.
3. גישת הריכוזיות
הרעיון בגישת הריכוזיות הוא ל שקול כל דמות כציר והתרחב בשני הכיוונים כדי למצוא פלינדרומים.
אנו נרחיב רק אם הדמויות בצד שמאל וימין מתאימות, ומסמיכות את המחרוזת לפלינדרום. אחרת, אנו ממשיכים לדמות הבאה.
בואו נראה הדגמה מהירה בה נתייחס לכל תו כמרכז לפלינדרום:
ציבורי הגדר findAllPalindromesUsingCenter (קלט מחרוזת) {Set palindromes = new HashSet (); עבור (int i = 0; i <input.length (); i ++) {palindromes.addAll (findPalindromes (input, i, i + 1)); palindromes.addAll (findPalindromes (קלט, i, i)); } להחזיר palindromes; }בתוך הלולאה שלמעלה, אנו מתרחבים לשני הכיוונים כדי לקבל את הסט של כל הפלינדרומים הממוקדים בכל עמדה. אנו מוצאים palindromes באורך שווה ומשונה על ידי קריאת השיטה findPalindromes פעמיים בלולאה:
הגדר פרטי FindPalindromes (קלט מחרוזת, int נמוך, int גבוה) {Set result = חדש HashSet (); ואילו (low> = 0 && high <input.length () && input.charAt (low) == input.charAt (high)) {result.add (input.substring (low, high + 1)); נָמוּך--; גבוה ++; } להחזיר תוצאה; }מורכבות הזמן של גישה זו היא O (n ^ 2). זהו שיפור ביחס לגישה הכוחית שלנו, אבל אנחנו יכולים לעשות אפילו טוב יותר, כפי שנראה בסעיף הבא.
4. האלגוריתם של Manacher
האלגוריתם של Manacherמוצא את המצע הפלינדרומי הארוך ביותר בזמן ליניארי. נשתמש באלגוריתם זה כדי למצוא את כל המצעים שהם פלינדרומים.
לפני שנצלול לאלגוריתם, נתחל כמה משתנים.
ראשית, נשמור על מחרוזת הקלט עם תו גבול בהתחלה ובסוף לפני המרת המחרוזת שהתקבלה למערך תווים:
מחרוזת formattedInput = "@" + קלט + "#"; char inputCharArr [] = formattedInput.toCharArray ();לאחר מכן נשתמש במערך דו מימדי רַדִיוּס עם שתי שורות - האחת לאחסון אורכי הפלינדרומים באורך מוזר, והשנייה לאחסון אורכי הפלינדרומים באורך אחיד:
רדיוס int [] [] = int int [2] [input.length () + 1];לאחר מכן, נחזור על מערך הקלט כדי למצוא את אורך הפלינדרום שבמרכזו אני ולאחסן אורך זה ב רַדִיוּס[][]:
הגדר palindromes = חדש HashSet (); מקסימום int; עבור (int j = 0; j <= 1; j ++) {רדיוס [j] [0] = max = 0; int i = 1; בעוד (i <= input.length ()) {palindromes.add (Character.toString (inputCharArr [i])); בעוד (inputCharArr [i - max - 1] == inputCharArr [i + j + max]) max ++; רדיוס [j] [i] = מקסימום; int k = 1; ואילו ((רדיוס [j] [i - k]! = מקסימום - k) && (k <מקס)) {רדיוס [j] [i + k] = מתמטיקה. min (רדיוס [j] [i - k], מקסימום - k); k ++; } max = Math.max (max - k, 0); i + = k; }}לבסוף נעבור במערך רַדִיוּס[][] לחישוב המצעים הפלינדרומיים שבמרכזם בכל עמדה:
עבור (int i = 1; i <= input.length (); i ++) {for (int j = 0; j 0; max--) {palindromes.add (input.substring (i - max - 1, max + j + i - 1)); }}}מורכבות הזמן של גישה זו היא O (n).
5. מסקנה
במאמר מהיר זה דנו במורכבות הזמן של גישות שונות למציאת משטחים שהם פלינדרומים.
כמו תמיד, קוד המקור המלא של הדוגמאות זמין באתר GitHub.
