Finden Sie die Länge des kleinsten Fensters, das alle Zeichen einer Zeichenfolge in einer anderen Zeichenfolge enthält

Kürzlich wurde ich interviewt. Ich habe es nicht gut gemacht, weil ich bei der folgenden Frage hängen geblieben bin

Angenommen, eine Sequenz ist gegeben: A D C B D A B C D A C D und die Suchsequenz ist wie folgt: A C D

Die Aufgabe bestand darin, den Start- und Endindex in der angegebenen Zeichenfolge zu finden, die alle Zeichen der Suchzeichenfolge enthält, wobei die Reihenfolge beibehalten wurde.

Ausgabe: unter der Annahme, dass der Index bei 1 beginnt:

Startindex 10 Endeindex 12

Erläuterung :

1. Start / Ende-Index ist nicht 1/3, da sie zwar die Zeichenfolge enthalten, die Reihenfolge jedoch nicht eingehalten wurde

2. Start / Ende-Index ist nicht 1/5, da sie zwar die Zeichenfolge in der Reihenfolge enthalten, die Länge jedoch nicht optimal ist

3. Start / Ende-Index ist nicht 6/9, da sie zwar die Zeichenfolge in der Reihenfolge enthalten, die Länge jedoch nicht optimal ist

Bitte gehen Sie durchWie finde ich die kleinste Teilzeichenfolge, die alle Zeichen einer bestimmten Zeichenfolge enthält?.

Die obige Frage ist jedoch anders, da die Reihenfolge nicht eingehalten wird. Ich kämpfe immer noch darum, die Indizes zu pflegen. Jede Hilfe wäre dankbar. Vielen Dank

Antworten auf die Frage(8)

Ihre Antwort auf die Frage