Kontroller, om to strenge er anagrammer i Java

1. Oversigt

Ifølge Wikipedia er et anagram et ord eller en sætning dannet ved at omarrangere bogstaverne i et andet ord eller en anden sætning.

Vi kan generalisere dette i strengbehandling ved at sige det et anagram af en streng er en anden streng med nøjagtig den samme mængde af hvert tegn i den, i en hvilken som helst rækkefølge.

I denne vejledning skal vi se på at detektere hele strenganagrammer, hvor mængden af ​​hvert tegn skal være ens, inklusive ikke-alfabetegn som mellemrum og cifre. For eksempel, "! Saltfattigt!" og “Ugler-lat !!” betragtes som anagrammer, da de indeholder nøjagtigt de samme tegn.

2. Løsning

Lad os sammenligne et par løsninger, der kan afgøre, om to strenge er anagrammer. Hver løsning kontrollerer i starten, om de to strenge har det samme antal tegn. Dette er en hurtig måde at afslutte tidligt siden input med forskellige længder kan ikke være anagrammer.

Lad os for hver mulig løsning se på implementeringskompleksiteten for os som udviklere. Vi vil også se på tidskompleksiteten for CPU'en ved hjælp af stor O-notation.

3. Kontroller ved at sortere

Vi kan omarrangere tegnene i hver streng ved at sortere deres tegn, som vil producere to normaliserede række af tegn.

Hvis to strenge er anagrammer, skal deres normaliserede former være de samme.

I Java kan vi først konvertere de to strenge til char [] arrays. Så kan vi sortere disse to arrays og kontrollere for lighed:

boolean isAnagramSort (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } char [] a1 = string1.toCharArray (); char [] a2 = string2.toCharArray (); Arrays.sort (a1); Arrays.sort (a2); returnere Arrays.equals (a1, a2); } 

Denne løsning er let at forstå og implementere. Den samlede driftstid for denne algoritme er dog O (n log n) fordi sortering af en række n tegn tager O (n log n) tid.

For at algoritmen skal fungere, skal den lave en kopi af begge inputstrenge som tegnrække ved hjælp af lidt ekstra hukommelse.

4. Kontroller ved at tælle

En alternativ strategi er at tælle antallet af forekomster af hvert tegn i vores input. Hvis disse histogrammer er ens mellem indgangene, er strengene anagrammer.

Lad os kun bygge et histogram for at spare lidt hukommelse. Vi forøger tællingerne for hvert tegn i den første streng og mindsker antallet for hvert tegn i det andet. Hvis de to strenge er anagrammer, bliver resultatet, at alt balancerer til 0.

Histogrammet har brug for en tabel med faste størrelser med optællinger med en størrelse defineret af tegnsætstørrelsen. For eksempel, hvis vi kun bruger en byte til at gemme hvert tegn, så kan vi bruge en tællende matrixstørrelse på 256 til at tælle forekomsten af ​​hvert tegn:

privat statisk int CHARACTER_RANGE = 256; public boolean isAnagramCounting (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } int antal [] = nye int [CHARACTER_RANGE]; for (int i = 0; i <string1.length (); i ++) {count [string1.charAt (i)] ++; tælle [streng2.charAt (i)] -; } for (int i = 0; i <CHARACTER_RANGE; i ++) {if (count [i]! = 0) {return false; }} returner sandt; }

Denne løsning er hurtigere med tidskompleksiteten af På). Det har dog brug for ekstra plads til tællearrayet. Ved 256 heltal er det ikke så dårligt for ASCII.

Men hvis vi har brug for at øge CHARACTER_RANGE for at understøtte tegnsæt med flere byte som UTF-8, ville dette blive meget hukommelseshungrigt. Derfor er det kun virkelig praktisk, når antallet af mulige tegn er i et lille interval.

Fra et udviklingssynspunkt indeholder denne løsning mere kode til vedligeholdelse og gør mindre brug af Java-biblioteksfunktioner.

5. Tjek med MultiSet

Vi kan forenkle tælle- og sammenligningsprocessen ved hjælp af MultiSet. MultiSet er en samling, der understøtter ordre-uafhængig lighed med duplikerede elementer. F.eks. Er multisættene {a, a, b} og {a, b, a} ens.

At bruge Multisæt, skal vi først tilføje Guava-afhængighed til vores projekt pom.xml fil:

 com.google.guava guava 28.1-jre 

Vi konverterer hver af vores inputstrenge til en MultiSet af tegn. Så kontrollerer vi, om de er ens:

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

Denne algoritme løser problemet i På) tid uden at skulle erklære et stort tællende array.

Det svarer til den tidligere tællerløsning. Men i stedet for at bruge en tabel med fast størrelse til at tælle, drager vi fordel af MutlitSet klasse for at simulere en tabel med variabel størrelse med et antal for hvert tegn.

Koden til denne løsning gør mere brug af biblioteksfunktioner på højt niveau end vores tælleløsning.

6. Brevbaseret anagram

Eksemplerne hidtil overholder ikke strengt den sproglige definition af et anagram. Dette skyldes, at de betragter tegnsætningstegn som en del af anagrammet, og de er store og små bogstaver.

Lad os tilpasse algoritmerne for at aktivere et bogstavsbaseret anagram. Lad os kun overveje omlægningen af ​​store og små bogstaver uanset andre tegn såsom hvide mellemrum og tegnsætning. For eksempel, “Et decimaltegn” og "Jeg er en prik på plads." ville være anagrammer over hinanden.

For at løse dette problem kan vi først forbehandle de to inputstrenge for at filtrere uønskede tegn ud og konvertere bogstaver til små bogstaver. Derefter kan vi bruge en af ​​ovenstående løsninger (f.eks MultiSet løsning) for at kontrollere anagrammer på de behandlede strenge:

Forbehandling af streng (strengkilde) {return source.replaceAll ("[^ a-zA-Z]", "") .toLowerCase (); } boolean isLetterBasedAnagramMultiset (String string1, String string2) {return isAnagramMultiset (preprocess (string1), preprocess (string2)); }

Denne tilgang kan være en generel måde at løse alle varianter af anagramproblemerne på. For eksempel, hvis vi også vil medtage cifre, er vi bare nødt til at justere forbehandlingsfilteret.

7. Konklusion

I denne artikel kiggede vi på tre algoritmer til kontrol af, om en given streng er et anagram med et andet, tegn for tegn. For hver løsning diskuterede vi kompromiserne mellem den krævede hastighed, læsbarhed og størrelse på hukommelsen.

Vi så også på, hvordan man tilpasser algoritmerne til at kontrollere for anagrammer i den mere traditionelle sproglige forstand. Vi opnåede dette ved at forbehandle input til små bogstaver.

Som altid er kildekoden til artiklen tilgængelig på GitHub.