Porównywanie dwóch ciągów znaków w języku Java i identyfikowanie duplikatów słów

Question

Próbuję móc porównać dwa ciągi znaków i zidentyfikować zduplikowane słowa. Na przykład;

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

Porównanie wartości String1 i String2 spowoduje zwrócenie słowa; "Nazwa".

Wiem, że możliwe jest podzielenie tych dwóch ciągów na tablicę słów, a następnie iterowanie po każdym słowie każdego ciągu w tablicy 2-D. Jest to jednak kosztowne obliczeniowo w O (n^2) i zastanawiałem się, czy istnieje szybszy sposób robienia tego?

Dzięki.

EDYCJA: Zmieniono przykład w celu zwiększenia czytelności.

Answer 1

Po zdobyciu struny do tablic słowo:

Możesz dodać wszystkie elementy w pierwszej tablicy do HashMap, a następnie zeskanować drugą tablicę aby sprawdzić, czy każdy z elementów istnieje w hashmap. Ponieważ czas dostępu do mapy mieszającej wynosi O (1), będzie to złożoność czasu O (n + m).

Jeśli nie chcesz używać dodatkowej spacji, możesz sortować obie tablice w O (nlogn), a następnie porównać elementy w O (n + m), co da w sumie O (nlogn).

Answer 2

Jednym prostym rozwiązaniem jest użycie metody Guawy Sets. To jest dość proste:

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); 

wyjściowa:

[name] 

Można również znaleźć więcej informacji na temat algorytmów wykrywania zestaw skrzyżowanie na this thread.