Finden Sie den längsten Teilstring, ohne Zeichen zu wiederholen

1. Übersicht

Vergleichen Sie in diesem Lernprogramm die Möglichkeiten, mit Java die längste Teilzeichenfolge eindeutiger Buchstaben zu finden. Die längste Teilzeichenfolge eindeutiger Buchstaben in „CODINGISAWESOME“ ist beispielsweise „NGISAWE“.

2. Brute-Force-Ansatz

Beginnen wir mit einem naiven Ansatz. Zunächst können wir jeden Teilstring untersuchen, ob er eindeutige Zeichen enthält:

String getUniqueCharacterSubstringBruteForce(String input) { String output = ""; for (int start = 0; start < input.length(); start++) { Set 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 es n * (n + 1) / 2 mögliche Teilzeichenfolgen gibt, ist die zeitliche Komplexität dieses Ansatzes O (n ^ 2) .

3. Optimierter Ansatz

Schauen wir uns nun einen optimierten Ansatz an. Wir beginnen, die Saite von links nach rechts zu durchlaufen und behalten den Überblick über:

  1. der aktuelle String mit nicht-wiederkehrenden Zeichen mit Hilfe eines Start- und End- Index
  2. die längste nicht wiederholende Teilzeichenausgabe
  3. eine Nachschlagetabelle mit bereits besuchten Zeichen
String getUniqueCharacterSubstring(String input) { Map 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; }

Für jeden neuen Charakter suchen wir ihn in den bereits besuchten Charakteren. Wenn das Zeichen bereits besucht wurde und Teil des aktuellen Teilstrings mit sich nicht wiederholenden Zeichen ist, aktualisieren wir den Startindex. Andernfalls werden wir den String weiter durchlaufen.

Da wir den String nur einmal durchlaufen, ist die Zeitkomplexität linear oder O (n) .

Dieser Ansatz wird auch als Schiebefenstermuster bezeichnet.

4. Testen

Lassen Sie uns abschließend unsere Implementierung gründlich testen, um sicherzustellen, dass sie funktioniert:

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

Hier versuchen wir, Randbedingungen sowie die typischeren Anwendungsfälle zu testen .

5. Schlussfolgerung

In diesem Tutorial haben wir gelernt, wie Sie mithilfe der Schiebefenstertechnik den längsten Teilstring mit sich nicht wiederholenden Zeichen finden.

Und wie immer ist der Quellcode auf GitHub verfügbar.