एक trie में सबसे लंबा शब्द कैसे खोजें?

Question

मुझे एक trie की अवधारणा को समझने में परेशानी हो रही है।

पूरे शब्द की वर्तनी यदि मैं यह सही ढंग से देखते हैं, एक Trie में सभी पत्र-गांठ है जाएगा और सभी माता पिता नोड्स पात्रों अंतिम पत्ती के लिए अग्रणी पकड़: "trie" विकिपीडिया प्रविष्टि से मैं इस तस्वीर नोड। तो, एक वर्ग DigitalTreeNode बुलाया

public class DigitalTreeNode { 
     public boolean isAWord; 
     public String wordToHere; (compiles all the characters in a word together) 
     public Map<String, DTN> children; 
} 

अगर मैं एक विधि है कि trie में सबसे लंबा शब्द देता है यह केवल प्रत्येक पत्ती नोड पर सबसे लंबा शब्द खोजने शामिल होगा लागू करने के लिए करना चाहता था द्वारा परिभाषित किया गया है, तो मैं है? मैं कैसे इस तरह के रूप में एक विधि लागू करना होगा:

public static String longestWord (DigitalTreeNode d); 

मैं इसे एक सबसे लंबे समय तक स्ट्रिंग वैरिएबल की स्थापना करना शामिल है, रिकर्सिवली प्रत्येक नोड के माध्यम से जा रहा है और पता चल सके कि यह एक शब्द है, अगर यह एक शब्द है अनुमान लगा रहा हूँ और यह की दूरी सबसे लंबे समय तक चरम = newWordLength से अधिक है। लेकिन, मुझे यकीन नहीं है कि मानचित्र बच्चे कैसे फिट बैठते हैं। उपरोक्त विधि का उपयोग करके मुझे किसी भी त्रिभुज में सबसे लंबा शब्द कैसे मिलेगा?

Answer 1

पत्ती नोड्स में आमतौर पर पूरी स्ट्रिंग नहीं होती है (हालांकि वे कर सकते हैं), कई बार ट्राई में, एक पत्ता नोड में केवल '$' चिह्न होता है यह इंगित करने के लिए कि यह स्ट्रिंग का अंत है।

ट्राई में सबसे लंबा शब्द खोजने के लिए आप पेड़ पर BFS का उपयोग कर सकते हैं, पहले "अंतिम" पत्ता ढूंढने के लिए। "आखिरी पत्ता" अंतिम तत्व है जो बीएफएस कतार से बाहर निकला था (इसके बाद इसे खाली कतार के साथ बंद किए गए बीएफएस के एल्गोरिदम को पॉप किया गया था)।
इस पत्ते से वास्तविक शब्द प्राप्त करने के लिए आपको पत्ते से वापस जड़ तक जाना होगा। This thread ने चर्चा की कि यह कैसे किया जा सकता है।

यह समाधान, O(|S| * n) वह जगह है जहाँ |S| एक स्ट्रिंग की औसत लंबाई है, और n डी एस में स्ट्रिंग की संख्या है।

आप trie डी एस में हेरफेर कर सकते हैं, मुझे लगता है यह बेहतर किया जा सकता है (लेकिन यह इस सवाल में मुद्दा नहीं लगता है)

छद्म कोड:

findLongest(trie): 
    //first do a BFS and find the "last node" 
    queue <- [] 
    queue.add(trie.root) 
    last <- nil 
    map <- empty map 
    while (not queue.empty()): 
    curr <- queue.pop() 
    for each son of curr: 
     queue.add(son) 
     map.put(son,curr) //marking curr as the parent of son 
    last <- curr 
    //in here, last indicate the leaf of the longest word 
    //Now, go up the trie and find the actual path/string 
    curr <- last 
    str = "" 
    while (curr != nil): 
     str = curr + str //we go from end to start 
     curr = map.get(curr) 
    return str