Java >> Java tutorial >  >> Tag >> char

Find den længste understreng uden gentagne tegn

char

1. Oversigt

I dette selvstudie kan du sammenligne måder at finde den længste understreng af unikke bogstaver ved hjælp af Java. For eksempel er den længste understreng af unikke bogstaver i "CODINGISAWESOME" "NGISAWE".

2. Brute Force Approach

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

String getUniqueCharacterSubstringBruteForce(String input) {
    String output = "";
    for (int start = 0; start < input.length(); start++) {
        Set<Character> visited = new HashSet<>();
        int end = start;
        for (; end < input.length(); end++) {
            char currChar = input.charAt(end);
            if (visited.contains(currChar)) {
                break;
            } else {
                visited.add(currChar);
            }
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end);
        }
    }
    return output;
}

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

3. Optimeret tilgang

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

  1. den aktuelle understreng med ikke-gentagende tegn ved hjælp af en start og slut indeks
  2. den længste ikke-gentagende understreng output
  3. en opslagstabel over allerede besøgte tegn 
String getUniqueCharacterSubstring(String input) {
    Map<Character, Integer> visited = new HashMap<>();
    String output = "";
    for (int start = 0, end = 0; end < input.length(); end++) {
        char currChar = input.charAt(end);
        if (visited.containsKey(currChar)) {
            start = Math.max(visited.get(currChar)+1, start);
        }
        if (output.length() < end - start + 1) {
            output = input.substring(start, end + 1);
        }
        visited.put(currChar, end);
    }
    return output;
}

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

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

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

4. Test

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

@Test
void givenString_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"));
}

Her forsøger vi at teste grænsebetingelser såvel som de mere typiske use cases .

5. Konklusion

I dette selvstudie har vi lært, hvordan du bruger glidende vinduesteknikken til at finde den længste understreng med ikke-gentagende tegn.

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


Java tag