streamalism.org

1. Áttekintés

Ebben az oktatóanyagban hasonlítsa össze az egyedi betűk leghosszabb részszövegének megkeresését a Java használatával. Például a „CODINGISAWESOME” egyedi betűinek leghosszabb alsora az „NGISAWE”.

2. Brute Force megközelítés

Kezdjük egy naiv megközelítéssel. Mindenekelőtt, megvizsgálhatjuk az egyes alszövegeket, hogy tartalmaznak-e egyedi karaktereket:

String getUniqueCharacterSubstringBruteForce (karakterlánc bemenet) {String output = ""; for (int start = 0; start <input.length (); start ++) {Meglátogatott készlet = new HashSet (); int vég = kezdet; for (; end <input.length (); end ++) {char currChar = input.charAt (end); if (meglátogatott.tartalmaz (currChar)) {törés; } else {meglátogatott.add (currChar); }} if (output.length () <end - start + 1) {output = input.substring (kezdet, end); }} visszatérő kimenet; }

Mivel vannak n * (n + 1) / 2 lehetséges alsorok, e megközelítés időbeli összetettsége az O (n ^ 2).

3. Optimalizált megközelítés

Most nézzünk meg egy optimalizált megközelítést. Megkezdjük a húr balról jobbra haladását, és nyomon követjük a következőket:

1. az aktuális szubsztring nem ismétlődő karakterekkel a segítségével Rajt és vége index
2. a leghosszabb nem ismétlődő részstring Kimenet
3. egy keresési táblázat már meglátogatta karakterek

String getUniqueCharacterSubstring (karakterlánc bevitele) {Meglátogatott térkép = új HashMap (); Karakterlánc kimenet = ""; for (int kezdet = 0, vég = 0; vég <bemenet.hossz (); vég ++) {char currChar = input.charAt (vég); if (meglátogatott.containsKey (currChar)) {start = Math.max (meglátogatott.get (currChar) +1, start); } if (output.length () <end - start + 1) {output = input.substring (start, end + 1); } meglátogatott.put (currChar, end); } visszatérő kimenet; }

Minden új karakter esetében a már meglátogatott karakterekben keressük. Ha a karaktert már meglátogattuk, és a jelenlegi, nem ismétlődő karaktereket tartalmazó részszöveg része, akkor frissítjük a kezdő indexet. Ellenkező esetben folytatjuk a húr bejárását.

Mivel csak egyszer haladunk át a húron, az idő bonyolultsága lineáris lesz, vagy Tovább).

Ez a megközelítés csúszóablakként is ismert.

4. Tesztelés

Végül teszteljük alaposan a megvalósításunkat, hogy megbizonyosodjunk arról, hogy működik-e:

@Test void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected () {assertEquals ("", getUniqueCharacterSubstring ("")); assertEquals ("A", getUniqueCharacterSubstring ("A")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("AABCDEF")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("ABCDEFF")); assertEquals ("NGISAWE", getUniqueCharacterSubstring ("CODINGISAWESOME")); assertEquals ("be kódolás", getUniqueCharacterSubstring ("mindig legyen kódoló")); }

Itt próbáljuk és teszt határfeltételek, valamint a tipikusabb felhasználási esetek.

5. Következtetés

Ebben az oktatóanyagban megtanultuk, hogyan kell használni a csúszóablakos technikát a leghosszabb, nem ismétlődő karakterekkel rendelkező részstruktúra megtalálásához.

És mint mindig, a forráskód is elérhető a GitHubon.