जांचें कि सूची में कोई तत्व जावा

Question

में अन्य का उपसर्ग है, तो मैं तारों की एक सूची को कार्यान्वित करना चाहता हूं और फिर सूची में सभी तत्वों की जांच करना चाहता हूं कि अगर कोई तत्व है जो सूची में अन्य तत्व का उपसर्ग है या नहीं । उदाहरण

[abc, cde, efg, cdetgh] 

उपरोक्त सूची में के लिए, "cde" (एक तत्व) अन्य तत्व "cdetgh" का उपसर्ग है। यदि संभव हो तो मैं पूरी सूची को पुन: सक्रिय नहीं करना चाहता हूं।

Answer 1

आपको पूरी सूची को फिर से शुरू करना होगा। निष्पक्ष दृष्टिकोण आपको सूची में प्रत्येक तत्व के लिए पूरी सूची को फिर से स्थापित करने के लिए मजबूर करेगा। यह एक ओ (एन^2) एल्गोरिदम है।

सूची के आकार और आवृत्ति को इस ऑपरेशन को करने के लिए आवश्यक आवृत्ति के आधार पर, यह स्वीकार्य हो सकता है। आप अंतरिक्ष की कीमत पर समय बचाने के लिए एक व्यापार बंद कर सकते हैं। प्रत्येक तत्व के माध्यम से जाएं, और प्रत्येक तत्व के लिए प्रत्येक उपसर्ग का हैशसेट बनाएं, और उसके बाद उपसर्ग में मौजूद तत्वों की जांच करें।

final Map<String, List<String>> prefixes = new HashMap<>(); 
for (final String element : list) { 
    // Go through every prefix that is at least 1 in length, 
    // but shorter than the current element). 
    for (int len = 1; len < element.length() - 1; ++len) { 
     final String prefix = element.substring(0, len); 
     List<String> hasPrefix = prefixes.get(prefix); 
     if (hasPrefix == null) { 
      hasPrefix = new ArrayList<>(); 
      prefixes.put(prefix, hasPrefix); 
     } 
     hasPrefix.add(element); 
    } 
} 

for (final String element : list) { 
    if (prefixes.containsKey(element)) { 
     System.out.printf("The element \"%s\" is a prefix of the following elements:\n%s", element, prefixes.get(element).toString()); 
    } 
} 

इस एल्गोरिथ्म हे (एन * एम) के समय में है, जहां एन सूची आकार है, और एम औसत तत्व लंबाई है। लेकिन थोड़ा और जगह लेता है। इसके लिए और भी अधिक कुशल समाधान हैं, लेकिन वे तेजी से जटिल हो जाते हैं, और परिमित राज्य मशीन निर्माण, या एक उपसर्ग पेड़ शामिल हैं।