מצא את המצע הארוך ביותר מבלי לחזור על דמויות
1. סקירה כללית
במדריך זה, השווה דרכים למצוא את המצע הארוך ביותר של אותיות ייחודיות באמצעות Java. לדוגמא, המצע הארוך ביותר של אותיות ייחודיות ב- "CODINGISAWESOME" הוא "NGISAWE".
2. גישת כוח הברוט
נתחיל בגישה נאיבית. להתחיל עם, אנו יכולים לבחון כל תשתית אם היא מכילה תווים ייחודיים:
מחרוזת getUniqueCharacterSubstringBruteForce (קלט מחרוזת) {String output = ""; עבור (int התחל = 0; התחל <input.length (); התחל ++) {הגדר ביקור = HashSet חדש (); int end = התחלה; עבור (; סוף <input.length (); end ++) {char currChar = input.charAt (end); אם (ביקור.כיל (currChar)) {הפסקה; } אחר {ביקר. הוסף (currChar); }} אם (output.length () <end - start + 1) {output = input.substring (start, end); }} פלט החזר; }מכיוון שיש n * (n + 1) / 2 מצעים אפשריים, מורכבות הזמן של גישה זו היא O (n ^ 2).
3. גישה אופטימלית
עכשיו, בואו נסתכל על גישה מותאמת. אנו מתחילים לחצות את המחרוזת משמאל לימין ועוקבים אחר:
- המצע הנוכחי עם תווים לא חוזרים בעזרת א הַתחָלָה ו סוֹף אינדקס
- המצע הארוך ביותר שאינו חוזר תְפוּקָה
- טבלת חיפוש כבר ביקר תווים
מחרוזת getUniqueCharacterSubstring (קלט מחרוזת) {מפה ביקרה = HashMap חדש (); פלט מחרוזת = ""; עבור (int התחלה = 0, סוף = 0; סוף <input.length (); סוף ++) {char currChar = input.charAt (סוף); אם (visit.containsKey (currChar)) {start = Math.max (visited.get (currChar) +1, start); } אם (output.length () <end - start + 1) {output = input.substring (start, end + 1); } visited.put (currChar, סוף); } פלט החזר; }עבור כל דמות חדשה, אנו מחפשים אותה בדמויות שכבר ביקרו בהן. אם התו כבר ביקר והוא חלק מהמצע הנוכחי עם תווים שאינם חוזרים, אנו מעדכנים את אינדקס ההתחלה. אחרת, נמשיך לחצות את המחרוזת.
מכיוון שאנחנו חוצים את המיתר רק פעם אחת, מורכבות הזמן תהיה ליניארית, או עַל).
גישה זו מכונה גם תבנית החלון הזזה.
4. בדיקות
לבסוף, בואו לבדוק ביסודיות את היישום שלנו כדי לוודא שהוא עובד:
@Test בטל givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected () {assertEquals ("", getUniqueCharacterSubstring ("")); assertEquals ("A", getUniqueCharacterSubstring ("A")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("AABCDEF")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("ABCDEFF")); assertEquals ("NGISAWE", getUniqueCharacterSubstring ("CODINGISAWESOME")); assertEquals ("להיות קידוד", getUniqueCharacterSubstring ("תמיד להיות קידוד")); }הנה, אנחנו מנסים ו לבדוק את תנאי הגבול וכן את מקרי השימוש האופייניים יותר.
5. מסקנה
במדריך זה למדנו כיצד להשתמש בטכניקת חלון הזזה כדי למצוא את המצע הארוך ביותר עם תווים שאינם חוזרים.
וכמו תמיד, קוד המקור זמין ב- GitHub.
