streamalism.org

1. Prehľad

V tomto tutoriále porovnajte spôsoby, ako nájsť najdlhší podreťazec jedinečných písmen pomocou Javy. Napríklad najdlhší podreťazec jedinečných písmen v reťazci „CODINGISAWESOME“ je „NGISAWE“.

2. Priblíženie hrubou silou

Začnime s naivným prístupom. Začať s, môžeme preskúmať každý podreťazec, či obsahuje jedinečné znaky:

Reťazec getUniqueCharacterSubstringBruteForce (reťazcový vstup) {reťazcový výstup = ""; for (int start = 0; start <input.length (); start ++) {Set navštívený = nový HashSet (); int koniec = štart; for (; end <input.length (); end ++) {charcurChar = input.charAt (end); if (navštívené.obsahuje (curChar)) {break; } else {navštívené.add (curChar); }} if (output.length () <end - start + 1) {output = input.substring (start, end); }} vratit vystup; }

Pretože existujú n * (n + 1) / 2 možné podreťazce, časová zložitosť tohto prístupu je O (n ^ 2).

3. Optimalizovaný prístup

Poďme sa teraz pozrieť na optimalizovaný prístup. Začneme prechádzať reťazcom zľava doprava a sledujeme:

1. aktuálny podreťazec s neopakujúcimi sa znakmi pomocou a začať a koniec index
2. najdlhší neopakujúci sa podreťazec výkon
3. vyhľadávacia tabuľka už navštívil znakov

Reťazec getUniqueCharacterSubstring (reťazcový vstup) {Navštívená mapa = nová HashMap (); Výstup reťazca = ""; for (int start = 0, end = 0; end <input.length (); end ++) {charcurChar = input.charAt (end); if (visit.containsKey (curChar)) {start = Math.max (navštívený.get (curChar) +1, štart); } if (output.length () <end - start + 1) {output = input.substring (start, end + 1); } navštívené.výstup (curChar, koniec); } návrat výstup; }

Pre každú novú postavu ju hľadáme v už navštívených postavách. Ak bol znak už navštívený a je súčasťou aktuálneho podreťazca s neopakujúcimi sa znakmi, aktualizujeme počiatočný index. V opačnom prípade budeme pokračovať v prechádzaní reťazca.

Pretože reťazec prechádzame iba raz, časová zložitosť bude lineárna, príp O (n).

Tento prístup je tiež známy ako vzor posuvného okna.

4. Testovanie

Na záver podrobne otestujme našu implementáciu, aby sme sa ubezpečili, že funguje:

@Test void givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExected () {assertEquals ("", getUniqueCharacterSubstring (""))); assertEquals ("A", getUniqueCharacterSubstring ("A")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("AABCDEF")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("ABCDEFF")); assertEquals ("NGISAWE", getUniqueCharacterSubstring ("CODINGISAWESOME")); assertEquals ("kódovať", getUniqueCharacterSubstring ("vždy kódovať")); }

Tu sa snažíme a skúšobné okrajové podmienky, ako aj typickejšie prípady použitia.

5. Záver

V tomto tutoriáli sme sa naučili, ako používať techniku ​​posuvného okna na nájdenie najdlhšieho podreťazca s neopakujúcimi sa znakmi.

A ako vždy je zdrojový kód k dispozícii na GitHub.