Sjekk om to strenger er anagrammer i Java

1. Oversikt

Ifølge Wikipedia er et anagram et ord eller en setning dannet ved å omorganisere bokstavene til et annet ord eller en annen setning.

Vi kan generalisere dette i strengbehandling ved å si det et anagram av en streng er en annen streng med nøyaktig samme mengde av hvert tegn i, i hvilken som helst rekkefølge.

I denne opplæringen skal vi se på å oppdage hele strenganagrammer hvor mengden av hvert tegn må være lik, inkludert ikke-alfa-tegn som mellomrom og sifre. For eksempel, "! Lite salt!" og "Ugler-lat !!" vil bli betraktet som anagrammer da de inneholder nøyaktig de samme tegnene.

2. Løsning

La oss sammenligne noen få løsninger som kan avgjøre om to strenger er anagrammer. Hver løsning vil sjekke i begynnelsen om de to strengene har samme antall tegn. Dette er en rask måte å gå ut tidlig siden innganger med forskjellige lengder kan ikke være anagrammer.

For hver mulig løsning, la oss se på implementeringskompleksiteten for oss som utviklere. Vi vil også se på tidskompleksiteten for CPU-en, ved hjelp av stor O-notasjon.

3. Merk av etter sortering

Vi kan omorganisere tegnene i hver streng ved å sortere karakterene deres, noe som gir to normaliserte matriser av tegn.

Hvis to strenger er anagrammer, bør de normaliserte formene være de samme.

I Java kan vi først konvertere de to strengene til røye [] arrays. Så kan vi sortere disse to matriser og sjekke for likhet:

boolsk isAnagramSort (strengstreng1, strengstreng2) {hvis (streng1.lengde ()! = streng2.lengde ()) {returner falsk; } char [] a1 = string1.toCharArray (); char [] a2 = string2.toCharArray (); Arrays.sort (a1); Arrays.sort (a2); retur Arrays. likestilling (a1, a2); } 

Denne løsningen er lett å forstå og implementere. Imidlertid er den totale kjøretiden til denne algoritmen O (n log n) fordi sortering av en rekke n tegn tar O (n log n) tid.

For at algoritmen skal fungere, må den lage en kopi av begge inngangsstrengene som tegnsett, ved å bruke litt ekstra minne.

4. Sjekk ved å telle

En alternativ strategi er å telle antall forekomster av hvert tegn i våre innganger. Hvis disse histogrammene er like mellom inngangene, er strengene anagrammer.

For å spare litt minne, la oss bygge bare ett histogram. Vi øker tellingen for hvert tegn i den første strengen, og reduserer antallet for hvert tegn i det andre. Hvis de to strengene er anagrammer, blir resultatet at alt balanserer til 0.

Histogrammet trenger en tabell med fast størrelse med tellinger med en størrelse definert av tegnsettstørrelsen. For eksempel, hvis vi bare bruker en byte til å lagre hvert tegn, så kan vi bruke en tellende matrisestørrelse på 256 for å telle forekomsten av hvert tegn:

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

Denne løsningen er raskere med tidskompleksiteten til På). Imidlertid trenger den ekstra plass for telleoppstillingen. På 256 heltall, for ASCII er det ikke så ille.

Men hvis vi trenger å øke CHARACTER_RANGE for å støtte tegnsett med flere byte som UTF-8, vil dette bli veldig minnehurtig. Derfor er det bare veldig praktisk når antallet mulige tegn er i et lite område.

Fra et utviklingssynspunkt inneholder denne løsningen mer kode å vedlikeholde og bruker mindre Java-biblioteksfunksjoner.

5. Sjekk med MultiSet

Vi kan forenkle tellings- og sammenligningsprosessen ved å bruke MultiSet. MultiSet er en samling som støtter ordreuavhengig likestilling med dupliserte elementer. For eksempel er flersettene {a, a, b} og {a, b, a} like.

Å bruke Multisett, må vi først legge til Guava-avhengigheten i prosjektet vårt pom.xml fil:

 com.google.guava guava 28.1-jre 

Vi vil konvertere hver av våre innspillstrenger til en MultiSet av tegn. Så sjekker vi om de er like:

boolsk isAnagramMultiset (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } Multisett 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 algoritmen løser problemet i På) tid uten å måtte erklære et stort tellende utvalg.

Det ligner på den forrige telleløsningen. Imidlertid, i stedet for å bruke en tabell med fast størrelse for å telle, utnytter vi MutlitSet klasse for å simulere en tabell med variabel størrelse, med en telling for hvert tegn.

Koden for denne løsningen gjør mer bruk av biblioteksfunksjoner på høyt nivå enn vår telleløsning.

6. Bokstavbasert anagram

Eksemplene så langt holder seg ikke strengt til den språklige definisjonen av et anagram. Dette er fordi de anser tegnsettingstegn som en del av anagrammet, og de er store og små bokstaver.

La oss tilpasse algoritmene for å aktivere et bokstavbasert anagram. La oss bare vurdere omorganiseringen av store og små bokstaver, uavhengig av andre tegn som hvite mellomrom og tegnsetting. For eksempel, “Et desimaltegn” og "Jeg er en prikk på plass." ville være anagrammer av hverandre.

For å løse dette problemet kan vi først behandle de to inndatstrengene for å filtrere ut uønskede tegn og konvertere bokstaver til små bokstaver. Da kan vi bruke en av løsningene ovenfor (si, MultiSet løsning) for å sjekke anagrammer på de behandlede strengene:

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

Denne tilnærmingen kan være en generell måte å løse alle varianter av anagramproblemene på. Hvis vi for eksempel også vil ha med sifre, trenger vi bare å justere forhåndsbehandlingsfilteret.

7. Konklusjon

I denne artikkelen så vi på tre algoritmer for å sjekke om en gitt streng er et anagram av en annen, karakter for karakter. For hver løsning diskuterte vi kompromissene mellom hastighet, lesbarhet og minnestørrelse som kreves.

Vi så også på hvordan vi kan tilpasse algoritmene for å se etter anagrammer i mer tradisjonell språklig forstand. Vi oppnådde dette ved å forhåndsbehandle inngangene til små bokstaver.

Som alltid er kildekoden for artikkelen tilgjengelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found