So sánh hai chuỗi trong java và xác định các từ trùng lặp

Question

Tôi đang cố gắng có thể so sánh hai Chuỗi và xác định các từ trùng lặp. Ví dụ;

String1 = "Hello, my name is John." 
String2 = "Can you tell me your name please?" 

So sánh chuỗi1 và chuỗi2 sẽ trả về từ; "Tên".

Tôi biết có thể chia hai chuỗi này thành một mảng từ và sau đó lặp lại từng từ của mỗi chuỗi trong một mảng 2-D. Tuy nhiên điều này là tốn kém tính toán tại O (n^2) và tôi đã tự hỏi nếu có một cách nhanh hơn để làm điều này?

Cảm ơn.

EDIT: Đã thay đổi ví dụ để rõ ràng.

Answer 1

Sau khi nhận được chuỗi để mảng từ:

Bạn có thể thêm tất cả các yếu tố trong mảng đầu tiên một hashmap và sau đó quét mảng thứ hai để xem nếu mỗi người trong số các yếu tố tồn tại trong hashmap. Vì thời gian truy cập vào một hashmap là O (1), đây sẽ là độ phức tạp thời gian O (n + m).

Nếu bạn không muốn sử dụng thêm không gian, bạn có thể sắp xếp cả hai mảng trong O (nlogn) và sau đó so sánh các mục trong O (n + m) sẽ cung cấp cho bạn tổng số O (nlogn).

Answer 2

Một giải pháp đơn giản là sử dụng phương pháp Sets.intersection của số Sets của ổi. Nó là khá dễ dàng:

String s1 = "Hello, my name is John."; 
String s2 = "Can you tell me your name?"; 
Splitter splitter = Splitter.onPattern("\\W").trimResults().omitEmptyStrings(); 
Set<String> intersection = Sets.intersection(// 
     Sets.newHashSet(splitter.split(s1)), // 
     Sets.newHashSet(splitter.split(s2))); 
System.out.println(intersection); 

Output:

[name] 

Bạn cũng có thể tìm thêm thông tin về thuật toán để phát hiện Set ngã tư trên this thread.