streamalism.org

1. Overzicht

Volgens Wikipedia is een anagram een ​​woord of zin die wordt gevormd door de letters van een ander woord of een andere zin te herschikken.

We kunnen dit generaliseren in stringverwerking door dat te zeggen een anagram van een string is een andere string met exact dezelfde hoeveelheid van elk teken erin, in willekeurige volgorde.

In deze tutorial gaan we kijken naar het detecteren van hele string-anagrammen waarbij de hoeveelheid van elk teken gelijk moet zijn, inclusief niet-alfa-tekens zoals spaties en cijfers. Bijvoorbeeld, "!Weinig zout!" en "Owls-lat !!" zouden als anagrammen worden beschouwd omdat ze exact dezelfde karakters bevatten.

2. Oplossing

Laten we een paar oplossingen vergelijken die kunnen beslissen of twee strings anagrammen zijn. Elke oplossing controleert aan het begin of de twee strings hetzelfde aantal karakters hebben. Dit is een snelle manier om sindsdien vroegtijdig te vertrekken ingangen met verschillende lengtes kunnen geen anagrammen zijn.

Laten we voor elke mogelijke oplossing kijken naar de complexiteit van de implementatie voor ons als ontwikkelaars. We zullen ook kijken naar de tijdcomplexiteit voor de CPU, met behulp van de grote O-notatie.

3. Controleer door te sorteren

We kunnen de karakters van elke string herschikken door hun karakters te sorteren, wat twee genormaliseerde arrays van karakters oplevert.

Als twee strings anagrammen zijn, zouden hun genormaliseerde vormen hetzelfde moeten zijn.

In Java kunnen we eerst de twee strings converteren naar char [] arrays. Vervolgens kunnen we deze twee arrays sorteren en op gelijkheid controleren:

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); retourneer Arrays.equals (a1, a2); } 

Deze oplossing is gemakkelijk te begrijpen en te implementeren. De totale looptijd van dit algoritme is echter O (n log n) omdat het sorteren van een reeks n karakters duurt O (n log n) tijd.

Om het algoritme te laten functioneren, moet het een kopie maken van beide invoertekenreeksen als tekenreeksen, met een beetje extra geheugen.

4. Controleer door te tellen

Een alternatieve strategie is om het aantal keren dat elk teken voorkomt in onze invoer te tellen. Als deze histogrammen gelijk zijn tussen de ingangen, dan zijn de strings anagrammen.

Laten we, om wat geheugen te besparen, slechts één histogram maken. We verhogen het aantal voor elk teken in de eerste tekenreeks en verlagen het aantal voor elk teken in de tweede tekenreeks. Als de twee strings anagrammen zijn, zal het resultaat zijn dat alles in evenwicht is met 0.

Het histogram heeft een tabel met tellingen met een vaste grootte nodig waarvan de grootte wordt bepaald door de grootte van de tekenset. Als we bijvoorbeeld slechts één byte gebruiken om elk teken op te slaan, kunnen we een telarraygrootte van 256 gebruiken om het voorkomen van elk teken te tellen:

privé statische int CHARACTER_RANGE = 256; openbare boolean isAnagramCounting (String string1, String string2) {if (string1.length ()! = string2.length ()) {return false; } int count [] = nieuwe int [CHARACTER_RANGE]; voor (int i = 0; i <string1.length (); i ++) {count [string1.charAt (i)] ++; tel [string2.charAt (i)] -; } for (int i = 0; i <CHARACTER_RANGE; i ++) {if (count [i]! = 0) {return false; }} retourneren waar; }

Deze oplossing is sneller met de tijdcomplexiteit van Aan). Het heeft echter extra ruimte nodig voor de telarray. Bij 256 gehele getallen is dat voor ASCII niet zo erg.

Als we echter moeten toenemen CHARACTER_RANGE om tekensets van meerdere bytes zoals UTF-8 te ondersteunen, zou dit erg geheugenverlies veroorzaken. Daarom is het alleen echt praktisch als het aantal mogelijke tekens in een klein bereik ligt.

Vanuit ontwikkelingsoogpunt bevat deze oplossing meer code om te onderhouden en maakt hij minder gebruik van Java-bibliotheekfuncties.

5. Neem contact op met MultiSet

We kunnen het tel- en vergelijkingsproces vereenvoudigen door gebruik te maken van MultiSet. MultiSet is een collectie die orderonafhankelijke gelijkheid ondersteunt met dubbele elementen. De multisets {a, a, b} en {a, b, a} zijn bijvoorbeeld gelijk.

Gebruiken Multiset, moeten we eerst de Guava-afhankelijkheid aan ons project toevoegen pom.xml het dossier:

 com.google.guava guave 28.1-jre 

We zullen elk van onze invoertekenreeksen omzetten in een MultiSet van karakters. Dan kijken we of ze gelijk zijn:

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

Dit algoritme lost het probleem op in Aan) tijd zonder een grote telarray te hoeven declareren.

Het is vergelijkbaar met de vorige teloplossing. In plaats van een tafel met een vast formaat te gebruiken om te tellen, profiteren we echter van de MutlitSet class om een ​​tabel met variabele afmetingen te simuleren, met een telling voor elk teken.

De code voor deze oplossing maakt meer gebruik van bibliotheekfuncties op hoog niveau dan onze teloplossing.

6. Anagram op basis van letters

De voorbeelden tot dusver volgen niet strikt de linguïstische definitie van een anagram. Dit komt omdat ze leestekens als onderdeel van het anagram beschouwen en ze zijn hoofdlettergevoelig.

Laten we de algoritmen aanpassen om een ​​op letters gebaseerd anagram mogelijk te maken. Laten we alleen kijken naar de herschikking van niet-hoofdlettergevoelige letters, ongeacht andere tekens, zoals spaties en leestekens. Bijvoorbeeld, "Een decimale punt" en "Ik ben een stip op zijn plaats." zouden anagrammen van elkaar zijn.

Om dit probleem op te lossen, kunnen we eerst de twee invoertekenreeksen voorbewerken om ongewenste tekens uit te filteren en letters om te zetten in kleine letters. Dan kunnen we een van de bovenstaande oplossingen gebruiken (bijvoorbeeld de MultiSet oplossing) om anagrammen op de verwerkte strings te controleren:

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

Deze benadering kan een algemene manier zijn om alle varianten van de anagramproblemen op te lossen. Als we bijvoorbeeld ook cijfers willen opnemen, hoeven we alleen het voorbewerkingsfilter aan te passen.

7. Conclusie

In dit artikel hebben we drie algoritmen bekeken om te controleren of een bepaalde tekenreeks een anagram is van een ander, teken voor teken. Voor elke oplossing bespraken we de afwegingen tussen de vereiste snelheid, leesbaarheid en grootte van het geheugen.

We hebben ook gekeken hoe we de algoritmen kunnen aanpassen om te controleren op anagrammen in de meer traditionele taalkundige zin. We hebben dit bereikt door de invoer voor te verwerken in kleine letters.

Zoals altijd is de broncode voor het artikel beschikbaar op GitHub.