Finden Sie, ob jedes Zeichen in einer Zeichenfolge in einer anderen Zeichenfolge vorhanden ist, schneller als O (n ^ 2)

Question

8

Gegeben 2 Strings:

%Vor%

Ich möchte herausfinden, ob jedes Zeichen in stringB H A T S in stringA

existiert

Bei einem Junior-Ansatz kann der Prozess innerhalb einer verschachtelten for-Schleife ausgeführt werden, deren Berechnungskomplexität O (n ^ 2) ist.

%Vor%

Ich suche nach einer schnelleren Lösung, um dieses Problem zu lösen.

java complexity-theory subset compare computation

Kone Man 05.08.2016, 17:26

quelle

1 Antwort

score 10 · Accepted Answer

Es gibt einen linearen Zeitalgorithmus.

Konvertiere dein stringA in einen Hash-Satz von Charakteren, die einen O (1) Mitgliedschaftstest haben.
Iterate über jedes Zeichen in stringB .
Wenn eines der Zeichen nicht in Ihrem Hash-Set ist, schlägt der Test fehl.
Wenn kein Fehler vorliegt, ist der Test erfolgreich.