Znajdź czy każda postać w 1 ciąg jest istnieć w innym ciągiem, szybciej niż O (n^2)

Question

Biorąc pod uwagę, że 2 ciągi:

String stringA = "WHATSUP"; 
String stringB = "HATS"; 

Chcę dowiedzieć się, czy każdy znak w stringB HATS istnieje w podejściu młodszym, proces można wykonać w zagnieżdżonej pętli for, której złożoność obliczeniowa wynosi O (n^2).

for(int i = 0; i < stringA.length(); i++){ 
    for(int j = 0; j < stringB.length(); j++){ 
     if(stringA.charAt(i) == stringB.charAt(j)) 
      //do something 
    } 
} 

Szukam szybszego rozwiązania, aby rozwiązać ten problem.

Answer 1

Istnieje algorytm liniowy czasu.

1. konwertować stringA do hash-zestaw znaków, który ma O (1) testowanie członkowskiej.
2. Powtórz poszczególne znaki w stringB.
3. Jeśli jeden z tych znaków nie znajduje się w twoim haszymdzie, test kończy się niepowodzeniem.
4. Jeśli nie ma niepowodzenia, test się powiódł.