हे की तुलना में तेजी 1 स्ट्रिंग में प्रत्येक चरित्र एक और स्ट्रिंग में मौजूद है या नहीं का पता लगाएं, (एन^2)

Question

यह देखते हुए कि 2 तार:

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

मैं STRING बिलियन H में ATS कि प्रत्येक चरित्र पता लगाना चाहते हैं stringA

जूनियर दृष्टिकोण में, प्रक्रिया को नेस्टेड फॉर-लूप के भीतर किया जा सकता है, इसकी गणना जटिलता ओ (एन^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 
    } 
} 

मैं इस समस्या को हल करने के लिए एक तेज़ समाधान की तलाश में हूं।

Answer 1

एक रैखिक समय एल्गोरिदम है।

1. अपने stringA को उन वर्णों के हैश-सेट में कनवर्ट करें जिनमें ओ (1) सदस्यता परीक्षण है।
2. stringB में प्रत्येक वर्ण पर Iterate।
3. यदि कोई वर्ण आपके हैश सेट में नहीं है, तो परीक्षण विफल हो जाता है।
4. यदि कोई विफलता नहीं है, तो परीक्षण सफल होता है।