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. Оптимизиран подход
Сега, нека да разгледаме оптимизиран подход. Започваме да обхождаме низа отляво надясно и поддържаме следите на:
- текущият подниз с неповтарящи се знаци с помощта на начален и краен индекс
- най-дългият неповтарящ се изход на подниз
- справочна таблица на вече посетени знаци
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.