जावा में दो स्ट्रिंग्स की तुलना करना और डुप्लिकेट शब्दों की पहचान

Question

मैं दो स्ट्रिंग्स की तुलना करने और डुप्लिकेट शब्दों की पहचान करने में सक्षम होने का प्रयास कर रहा हूं। उदाहरण के लिए;

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

स्ट्रिंग 1 और स्ट्रिंग 2 की तुलना शब्द को वापस कर देगा; "नाम"।

मुझे पता है कि इन दो तारों को शब्दों की एक सरणी में विभाजित करना संभव है, और उसके बाद प्रत्येक स्ट्रिंग के प्रत्येक शब्द को 2-डी सरणी में दोहराएं। हालांकि यह ओ (एन^2) में कम्प्यूटेशनल रूप से महंगा है और मैं सोच रहा था कि ऐसा करने का एक तेज तरीका है या नहीं?

धन्यवाद।

संपादित करें: स्पष्टता के लिए उदाहरण बदल दिया।

Answer 1

शब्द सरणियों को तार मिलने के बाद:

आप एक hashmap के लिए पहली सरणी में सभी तत्वों को जोड़ सकते हैं और उसके बाद दूसरी सरणी स्कैन देखने के लिए कि तत्वों में से प्रत्येक के hashmap में मौजूद है। चूंकि हैशपैप तक पहुंच का समय ओ (1) है, यह ओ (एन + एम) समय जटिलता होगी।

यदि आप अतिरिक्त स्थान का उपयोग नहीं करना चाहते हैं, तो आप ओ (nlogn) में दोनों सरणी को सॉर्ट कर सकते हैं और फिर ओ (एन + एम) में आइटम की तुलना कर सकते हैं जो आपको कुल में O (nlogn) देगा।

Answer 2

एक सरल समाधान Sets.intersection विधि का उपयोग गुवा के Sets का उपयोग करना है। यह बहुत आसान है:

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

आउटपुट:

[name] 

तुम भी एल्गोरिदम बारे में अधिक जानकारी this thread पर सेट चौराहे पता लगाने के लिए मिल सकता है।