Znajdź długość najmniejszego okna, które zawiera wszystkie znaki ciągu w innym ciągu
Ostatnio zostałem przesłuchany. Nie zrobiłem dobrze, bo utknąłem na następującym pytaniu
przypuśćmy, że podana jest sekwencja: A D C B D A B C D A C D i sekwencja wyszukiwania jest następująca: A C D
zadaniem było znalezienie indeksu początkowego i końcowego w podanym łańcuchu, który zawiera wszystkie znaki szukanego ciągu zachowujące kolejność.
Wydajność: zakładając, że indeks zaczyna się od 1:
początek indeksu 10 koniec indeksu 12
wyjaśnienie :
Indeks 1.start / end nie są odpowiednio 1/3, ponieważ zawierają ciąg, ale kolejność nie została zachowana
2.start / end index nie są odpowiednio 1/5, ponieważ zawierają ciąg w kolejności, ale długość nie jest optymalna
3.start / end index nie są odpowiednio 6/9, ponieważ zawierają ciąg w kolejności, ale długość nie jest optymalna
Proszę przejśćJak znaleźć najmniejszy podciąg zawierający wszystkie znaki z danego ciągu?.
Ale powyższe pytanie jest inne, ponieważ kolejność nie jest zachowana. Nadal walczę o utrzymanie indeksów. Każda pomoc byłaby doceniana. dzięki