Намерете най-дългия подниз без повтарящи се символи

Програмиране

1. Общ преглед

В този урок сравнете начините за намиране на най-дългия подниз от уникални букви с помощта на Java. Например, най-дългият подниз от уникални букви в „CODINGISAWESOME“ е „NGISAWE“.

2. Подход на грубата сила

Нека започнем с наивен подход. Като начало можем да разгледаме всеки подниз дали съдържа уникални символи:

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; }

Тъй като има n * (n + 1) / 2 възможни поднизове, сложността във времето на този подход е O (n ^ 2) .

3. Оптимизиран подход

Сега, нека да разгледаме оптимизиран подход. Започваме да обхождаме низа отляво надясно и поддържаме следите на:

  1. текущият подниз с неповтарящи се знаци с помощта на начален и краен индекс
  2. най-дългият неповтарящ се изход на подниз
  3. справочна таблица на вече посетени знаци
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; }

За всеки нов герой го търсим във вече посетените герои. Ако знакът вече е бил посетен и е част от текущия подниз с неповтарящи се символи, ние актуализираме началния индекс. В противен случай ще продължим да обхождаме низа.

Тъй като обхождаме низа само веднъж, сложността на времето ще бъде линейна или O (n) .

Този подход е известен също като модел на плъзгащия се прозорец.

4. Тестване

И накрая, нека тестваме цялостно нашето внедряване, за да се уверим, че работи:

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

Тук се опитваме да тестваме гранични условия, както и по-типичните случаи на употреба .

5. Заключение

В този урок научихме как да използваме техниката на плъзгащия прозорец, за да намерим най-дългия подниз с неповтарящи се символи.

И както винаги, изходният код е достъпен в GitHub.