streamalism.org

1. Prehľad

Podľa Wikipédie je anagram slovom alebo slovným spojením, ktoré vznikne preusporiadaním písmen iného slova alebo slovného spojenia.

Môžeme to zovšeobecniť pri spracovaní reťazcov tým, že to povieme anagram reťazca je ďalší reťazec, ktorý obsahuje presne rovnaké množstvo každého znaku v ľubovoľnom poradí.

V tomto výučbe sa pozrieme na zisťovanie anagramov celého reťazca, kde musí byť počet znakov rovnaký, vrátane znakov iných ako alfa, ako sú medzery a číslice. Napríklad, "! S nízkym obsahom soli!" a "Sovy-lat !!" by sa považovali za anagramy, pretože obsahujú úplne rovnaké znaky.

2. Riešenie

Porovnajme niekoľko riešení, ktoré môžu rozhodnúť, či sú dva reťazce anagramy. Každé riešenie na začiatku skontroluje, či majú dva reťazce rovnaký počet znakov. Toto je rýchly spôsob, ako skoro ukončiť vstupy s rôznymi dĺžkami nemôžu byť anagramy.

Pri každom možnom riešení sa pozrime na implementačnú zložitosť pre nás ako vývojárov. Pozrime sa tiež na časovú zložitosť procesora pomocou veľkej O-notácie.

3. Skontrolujte podľa zoradenia

Znaky každého reťazca môžeme usporiadať zoradením ich znakov, čím vzniknú dve normalizované polia znakov.

Ak sú dva reťazce anagramy, ich normalizované tvary by mali byť rovnaké.

V Jave môžeme najskôr previesť tieto dva reťazce char [] polia. Potom môžeme zoradiť tieto dve polia a skontrolovať rovnosť:

boolean isAnagramSort (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } char [] a1 = string1.toCharArray (); char [] a2 = string2.toCharArray (); Zoskupenia (al); Polia triediť (a2); return Arrays.equals (a1, a2); } 

Toto riešenie je ľahko pochopiteľné a implementovateľné. Celková doba prevádzky tohto algoritmu je však O (n log n) pretože triedenie poľa n znakov O (n log n) čas.

Aby algoritmus fungoval, musí vytvoriť kópiu oboch vstupných reťazcov ako pole znakov s využitím trochy pamäte navyše.

4. Skontrolujte počítaním

Alternatívnou stratégiou je spočítať počet výskytov jednotlivých znakov v našich vstupoch. Ak sú tieto histogramy medzi vstupmi rovnaké, potom sú reťazce anagramy.

Aby sme ušetrili trochu pamäte, zostavme si iba jeden histogram. V prvom reťazci zvýšime počet pre každý znak a v druhom znížime počet pre každý znak. Ak sú tieto dva reťazce anagramy, výsledkom bude, že všetko sa vyrovná s 0.

Histogram vyžaduje tabuľku počtov pevnej veľkosti s veľkosťou definovanou veľkosťou znakovej sady. Napríklad, ak na uloženie každého znaku použijeme iba jeden bajt, môžeme na výpočet výskytu každého znaku použiť veľkosť počítacieho poľa 256:

private static int CHARACTER_RANGE = 256; public boolean isAnagramCounting (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } počet int [] = nový int [CHARACTER_RANGE]; pre (int i = 0; i <string1.length (); i ++) {count [string1.charAt (i)] ++; count [string2.charAt (i)] -; } for (int i = 0; i <CHARACTER_RANGE; i ++) {if (count [i]! = 0) {return false; }} návrat true; }

Toto riešenie je s časovou zložitosťou rýchlejšie O (n). Potrebuje však ďalší priestor na počítanie poľa. Pri 256 celých číslach to pre ASCII nie je tak zlé.

Ak však potrebujeme zvýšiť CHARACTER_RANGE na podporu viacbajtových znakových sád, ako je UTF-8, by to stalo veľmi náročné na pamäť. Preto je to skutočne praktické, iba ak je počet možných znakov malý.

Z vývojového hľadiska obsahuje toto riešenie viac kódu na údržbu a menej využíva funkcie knižnice Java.

5. Skontrolovať s MultiSet

Proces počítania a porovnávania môžeme zjednodušiť použitím MultiSet. MultiSet je kolekcia, ktorá podporuje rovnosť nezávislú od objednávky s duplicitnými prvkami. Napríklad multisety {a, a, b} a {a, b, a} sú rovnaké.

Použit Multiset, najskôr musíme do nášho projektu pridať závislosť na Guave pom.xml spis:

 com.google.guava guava 28,1-jre 

Každý z našich vstupných reťazcov prevedieme na a MultiSet znakov. Potom skontrolujeme, či sú si rovné:

boolean isAnagramMultiset (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } Multiset multiset1 = HashMultiset.create (); Multiset multiset2 = HashMultiset.create (); pre (int i = 0; i <string1.length (); i ++) {multiset1.add (string1.charAt (i)); multiset2.add (string2.charAt (i)); } return multiset1.equals (multiset2); } 

Tento algoritmus rieši problém v O (n) bez toho, aby ste museli deklarovať veľké počítacie pole.

Je to podobné ako v predchádzajúcom riešení počítania. Namiesto počítania tabuliek s pevnou veľkosťou však využívame výhody MutlitSet triedy na simuláciu tabuľky s premenlivou veľkosťou, s počtom pre každý znak.

Kód tohto riešenia viac využíva možnosti knižnice na vysokej úrovni ako naše počítacie riešenie.

6. Anagram založený na písmenách

Príklady doposiaľ striktne nedodržiavajú jazykovú definíciu anagramu. Je to tak preto, lebo interpunkčné znaky považujú za súčasť anagramu a rozlišujú veľké a malé písmená.

Poďme prispôsobiť algoritmy tak, aby umožňovali anagramy založené na písmenách. Uvažujme iba o zmene usporiadania písmen, v ktorých sa nerozlišujú malé a veľké písmená, bez ohľadu na ďalšie znaky, ako sú medzery a interpunkčné znamienka. Napríklad, „Desatinná čiarka“ a "Som bodka na mieste." boli by si navzájom anagramy.

Aby sme tento problém vyriešili, môžeme najskôr pripraviť dva vstupné reťazce na filtrovanie nežiaducich znakov a na prevod malých písmen na malé písmená. Potom môžeme použiť jedno z vyššie uvedených riešení (napríklad MultiSet riešenie) na kontrolu anagramov na spracovaných reťazcoch:

Prepracovanie reťazca (zdroj reťazca) {return source.replaceAll ("[^ a-zA-Z]", "") .toLowerCase (); } boolean isLetterBasedAnagramMultiset (String string1, String string2) {return isAnagramMultiset (preprocess (string1), preprocess (string2)); }

Tento prístup môže predstavovať všeobecný spôsob riešenia všetkých variantov problémov s anagrammi. Napríklad, ak chceme zahrnúť aj číslice, stačí upraviť filter predspracovania.

7. Záver

V tomto článku sme sa zaoberali tromi algoritmami na kontrolu toho, či je daný reťazec anagramom iného znaku za znakom. Pre každé riešenie sme diskutovali o kompromisoch medzi požadovanou rýchlosťou, čitateľnosťou a veľkosťou pamäte.

Pozreli sme sa tiež na to, ako prispôsobiť algoritmy na kontrolu anagramov v tradičnejšom lingvistickom zmysle. Dosiahli sme to predbežným spracovaním vstupov na malé písmená.

Zdrojový kód článku je ako vždy k dispozícii na stránkach GitHub.