streamalism.org

1. Oversigt

I denne vejledning skal du sammenligne måder at finde den længste understreng med unikke bogstaver ved hjælp af Java. For eksempel er den længste delstreng af unikke bogstaver i “CODINGISAWESOME” “NGISAWE”.

2. Brute Force-tilgang

Lad os starte med en naiv tilgang. Til at starte med, vi kan undersøge hvert understreng, om det indeholder unikke tegn:

String getUniqueCharacterSubstringBruteForce (String input) {String output = ""; for (int start = 0; start <input.length (); start ++) {Set visited = new HashSet (); int slut = start; for (; end <input.length (); end ++) {char currChar = input.charAt (end); hvis (besøgt. indeholder (currChar)) {pause; } andet {besøgt.add (currChar); }} hvis (output.length () <slut - start + 1) {output = input.substring (start, slut); }} returnere output; }

Da der er n * (n + 1) / 2 mulige underlag, tidskompleksiteten af ​​denne tilgang er O (n ^ 2).

3. Optimeret tilgang

Lad os nu se på en optimeret tilgang. Vi begynder at krydse strengen fra venstre mod højre og holder styr på:

1. det aktuelle underlag med ikke-gentagne tegn ved hjælp af en Start og ende indeks
2. det længste ikke-gentagne underlag produktion
3. en opslagstabel over allerede besøgte tegn

Streng getUniqueCharacterSubstring (strengindgang) {Kort besøgt = nyt HashMap (); Strengoutput = ""; for (int start = 0, end = 0; end <input.length (); end ++) {char currChar = input.charAt (end); hvis (visited.containsKey (currChar)) {start = Math.max (besøgt.get (currChar) +1, start); } hvis (output.length () <end - start + 1) {output = input.substring (start, end + 1); } besøgt.put (currChar, slut); } returnere output; }

For hver ny karakter ser vi efter den i de allerede besøgte tegn. Hvis tegnet allerede er besøgt og er en del af det aktuelle underlag med ikke-gentagne tegn, opdaterer vi startindekset. Ellers fortsætter vi med at krydse strengen.

Da vi kun krydser strengen én gang, tidskompleksiteten vil være lineær, eller På).

Denne tilgang er også kendt som det glidende vinduesmønster.

4. Testning

Lad os endelig teste vores implementering grundigt for at sikre, at den fungerer:

@Test ugyldigt givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected () {assertEquals ("", getUniqueCharacterSubstring ("")); assertEquals ("A", getUniqueCharacterSubstring ("A")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("AABCDEF")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("ABCDEFF")); assertEquals ("NGISAWE", getUniqueCharacterSubstring ("CODINGISAWESOME")); assertEquals ("vær kodning", getUniqueCharacterSubstring ("vær altid kodning")); }

Her prøver vi test grænsebetingelser samt de mere typiske brugssager.

5. Konklusion

I denne vejledning har vi lært, hvordan man bruger skydevindueteknikken til at finde den længste understreng med ikke-gentagne tegn.

Og som altid er kildekoden tilgængelig på GitHub.