streamalism.org

1. Overzicht

Vergelijk in deze zelfstudie manieren om met Java de langste deelstring van unieke letters te vinden. De langste deelstring van unieke letters in "CODINGISAWESOME" is bijvoorbeeld "NGISAWE".

2. Brute Force-aanpak

Laten we beginnen met een naïeve benadering. Beginnen met, we kunnen elke subtekenreeks onderzoeken of deze unieke tekens bevat:

String getUniqueCharacterSubstringBruteForce (String-invoer) {String-uitvoer = ""; for (int start = 0; start <input.length (); start ++) {Set bezocht = nieuwe HashSet (); int end = start; for (; end <input.length (); end ++) {char currChar = input.charAt (end); if (bezocht.contains (currChar)) {pauze; } anders {bezocht.add (currChar); }} if (output.length () <end - start + 1) {output = input.substring (start, end); }} terugkeer output; }

Aangezien er zijn n * (n + 1) / 2 mogelijke ondergronden, de tijdcomplexiteit van deze benadering is O (n ^ 2).

3. Geoptimaliseerde aanpak

Laten we nu eens kijken naar een geoptimaliseerde aanpak. We beginnen de string van links naar rechts te doorlopen en houden het volgende bij:

1. de huidige substring met niet-herhalende karakters met behulp van een begin en einde inhoudsopgave
2. de langste niet-herhalende deelstring output
3. een opzoektabel van reeds bezocht karakters

String getUniqueCharacterSubstring (String-invoer) {Map bezocht = nieuwe HashMap (); String output = ""; for (int start = 0, end = 0; end <input.length (); end ++) {char currChar = input.charAt (end); if (bezocht.containsKey (currChar)) {start = Math.max (bezocht.get (currChar) +1, start); } if (output.length () <end - start + 1) {output = input.substring (start, end + 1); } bezocht.put (currChar, end); } terugkeer output; }

Voor elk nieuw personage zoeken we het in de reeds bezochte karakters. Als het teken al is bezocht en deel uitmaakt van de huidige substring met niet-herhalende tekens, werken we de startindex bij. Anders gaan we door met het doorlopen van de string.

Omdat we de string maar één keer doorlopen, de tijdcomplexiteit zal lineair zijn, of Aan).

Deze benadering wordt ook wel het schuifraampatroon genoemd.

4. Testen

Laten we tot slot onze implementatie grondig testen om er zeker van te zijn dat deze werkt:

@Test ongeldig gegevenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected () {assertEquals ("", getUniqueCharacterSubstring ("")); assertEquals ("A", getUniqueCharacterSubstring ("A")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("AABCDEF")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("ABCDEFF")); assertEquals ("NGISAWE", getUniqueCharacterSubstring ("CODINGISAWESOME")); assertEquals ("be coding", getUniqueCharacterSubstring ("always be coding")); }

Hier proberen we en test randvoorwaarden evenals de meer typische gebruikssituaties.

5. Conclusie

In deze zelfstudie hebben we geleerd hoe we de schuifvenstertechniek kunnen gebruiken om de langste deelstring met niet-herhalende tekens te vinden.

En, zoals altijd, is de broncode beschikbaar op GitHub.