Tìm xem mỗi nhân vật trong 1 chuỗi được tồn tại trong một chuỗi khác, nhanh hơn so với O (n^2)

Question

Cho rằng 2 chuỗi:

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

tôi muốn tìm hiểu xem mỗi nhân vật trong stringB HATS tồn tại trong stringA

Trong phương pháp tiếp cận cơ sở, quy trình có thể được thực hiện trong vòng lặp lồng nhau mà độ phức tạp tính toán của nó là 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 
    } 
} 

Tôi đang tìm giải pháp nhanh hơn để giải quyết vấn đề này.

Answer 1

Có một thuật toán thời gian tuyến tính.

1. Chuyển đổi số stringA thành nhóm băm ký tự có thử nghiệm thành viên O (1).
2. Lặp lại từng ký tự trong stringB.
3. Nếu một trong các ký tự không nằm trong bộ băm của bạn, thử nghiệm không thành công.
4. Nếu không có lỗi, thử nghiệm thành công.