streamalism.org

1. Prehľad

V tejto príručke sa dozvieme, ako skontrolovať, či reťazec obsahuje všetky písmená abecedy alebo nie.

Tu je rýchly príklad: „Farmársky jack si uvedomil, že veľké žlté periny sú drahé.”- ktorý skutočne obsahuje všetky písmená abecedy.

Budeme diskutovať o troch prístupoch.

Najskôr modelujeme algoritmus imperatívnym prístupom. Potom použije regulárne výrazy. A nakoniec využijeme deklaratívnejší prístup využívajúci Java 8.

Ďalej budeme diskutovať o zložitosti Big-O použitých prístupov.

2. Imperatívny algoritmus

Implementujme imperatívny algoritmus. Najskôr vytvoríme navštívené logické pole. Potom si prejdeme vstupný reťazec znak po znaku a označíme znak ako navštívený.

Vezmite prosím na vedomie, že Veľké písmená a Malými písmenami sa považujú za rovnaké. Takže index 0 predstavuje A aj a rovnako index 25 predstavuje Z aj z.

Nakoniec skontrolujeme, či sú všetky znaky v navštívenom poli nastavené na hodnotu true:

verejná trieda EnglishAlphabetLetters {public static boolean checkStringForAllTheLetters (reťazcový vstup) {int index = 0; boolean [] navštívil = nový boolean [26]; pre (int id = 0; id <input.length (); id ++) {if ('a' <= input.charAt (id) && input.charAt (id) <= 'z') {index = input.charAt (id) - „a“; } else if ('A' <= input.charAt (id) && input.charAt (id) <= 'Z') {index = input.charAt (id) - 'A'; } navštívil [index] = true; } for (int id = 0; id <26; id ++) {if (! navštívený [id]) {return false; }} návrat true; }}

Big-O-zložitosť tohto programu je O (n) kde n je dĺžka šnúrky.

Všimnite si, že existuje veľa spôsobov, ako optimalizovať algoritmus, ako napríklad odstránenie písmen zo sady a prerušenie čo najskôr Nastaviť je prázdny. Na účely tohto cvičenia je však tento algoritmus dosť dobrý.

3. Používanie regulárneho výrazu

Pomocou regulárneho výrazu môžeme ľahko dosiahnuť rovnaké výsledky pomocou niekoľkých riadkov kódu:

public static boolean checkStringForAllLetterUsingRegex (reťazcový vstup) {návratový vstup.toLowerCase () .replaceAll ("[^ az]", "") .replaceAll ("(.) (? =. * \ 1)", ""). dĺžka () == 26; }

Tu najskôr vylúčime všetky znaky okrem písmen abecedy z vstup. Potom odstraňujeme duplicitné znaky. Na záver spočítame listy a ubezpečíme sa, že ich máme všetky, 26.

Aj keď je to menej výkonné, Big-O-zložitosť tohto prístupu má tendenciu tiež k O (n).

4. Stream Java 8

Pomocou funkcií Java 8 môžeme ľahko dosiahnuť rovnaký výsledok kompaktnejším a deklaratívnym spôsobom pomocou Streamu filter a odlišný metódy:

public static boolean checkStringForAllLetterUsingStream (reťazcový vstup) {long c = input.toLowerCase (). chars () .filter (ch -> ch> = 'a' && ch <= 'z') .distinct () .count (); návrat c == 26; }

Veľká-O-zložitosť tohto prístupu bude tiež O (n).

4. Testovanie

Vyskúšajme šťastnú cestu k nášmu algoritmu:

@Test public void givenString_whenContainsAllCharacter_thenTrue () {Reťazec vety = "Farmársky jack si uvedomil, že veľké žlté paplóny sú drahé"; assertTrue (EnglishAlphabetLetters.checkStringForAllTheLetters (veta)); }

Tu, veta obsahuje všetky písmená abecedy, teda očakávame pravda ako výsledok.

5. Záver

V tomto výučbe sme sa venovali tomu, ako skontrolovať, či reťazec obsahuje všetky písmená abecedy.

Videli sme niekoľko spôsobov, ako to najskôr implementovať pomocou tradičného imperatívneho programovania, regulárnych výrazov a tokov Java 8.

Celý zdrojový kód je k dispozícii na GitHub.