streamalism.org

1. Oversikt

I denne veiledningen kan du sammenligne måter å finne den lengste delen av unike bokstaver ved hjelp av Java. For eksempel er den lengste delstrengen av unike bokstaver i “CODINGISAWESOME” “NGISAWE”.

2. Brute Force-tilnærming

La oss starte med en naiv tilnærming. Til å begynne med, vi kan undersøke hvert underlag om det inneholder unike tegn:

String getUniqueCharacterSubstringBruteForce (String input) {String output = ""; for (int start = 0; start <input.length (); start ++) {Sett besøkt = nytt HashSet (); int slutt = start; for (; slutt <input.length (); slutt ++) {char currChar = input.charAt (slutt); hvis (besøkt. inneholder (currChar)) {pause; } annet {besøkt.add (currChar); }} if (output.length () <end - start + 1) {output = input.substring (start, end); }} returnere utdata; }

Siden det er n * (n + 1) / 2 mulige underlag, tidskompleksiteten til denne tilnærmingen er O (n ^ 2).

3. Optimalisert tilnærming

La oss nå se på en optimalisert tilnærming. Vi begynner å krysse strengen fra venstre til høyre og holder styr på:

1. gjeldende substring med ikke-gjentakende tegn ved hjelp av a start og slutt indeks
2. det lengste ikke-gjentatte underlaget produksjon
3. et oppslagstabell av allerede besøkt tegn

String getUniqueCharacterSubstring (String input) {Map visited = new HashMap (); Strengutgang = ""; for (int start = 0, end = 0; end <input.length (); end ++) {char currChar = input.charAt (end); hvis (visit.containsKey (currChar)) {start = Math.max (visited.get (currChar) +1, start); } hvis (output.length () <end - start + 1) {output = input.substring (start, end + 1); } besøkte.put (currChar, slutt); } returnere utdata; }

For hver nye karakter ser vi etter den i de allerede besøkte tegnene. Hvis tegnet allerede har blitt besøkt og er en del av gjeldende delstreng med ikke-gjentatte tegn, oppdaterer vi startindeksen. Ellers fortsetter vi å krysse strengen.

Siden vi bare krysser strengen en gang, tidskompleksiteten vil være lineær, eller På).

Denne tilnærmingen er også kjent som skyvevindusmønsteret.

4. Testing

Til slutt, la oss teste gjennomføringen grundig for å sikre at den fungerer:

@Test ugyldig givenString_whenGetUniqueCharacterSubstringCalled_thenResultFoundAsExpected () {assertEquals ("", getUniqueCharacterSubstring ("")); assertEquals ("A", getUniqueCharacterSubstring ("A")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("AABCDEF")); assertEquals ("ABCDEF", getUniqueCharacterSubstring ("ABCDEFF")); assertEquals ("NGISAWE", getUniqueCharacterSubstring ("CODINGISAWESOME")); assertEquals ("vær koding", getUniqueCharacterSubstring ("vær alltid kodende")); }

Her prøver vi og testgrenseforhold så vel som de mer typiske brukssakene.

5. Konklusjon

I denne opplæringen har vi lært hvordan du bruker skyvevindueteknikken for å finne den lengste substringen med ikke-gjentatte tegn.

Og som alltid er kildekoden tilgjengelig på GitHub.