मान लीजिए हमें तीन बेसिक ऑपरेशन्स जैसे insert(), search(), startsWith() मेथड्स के साथ Trie स्ट्रक्चर बनाना है। हम मान सकते हैं कि सभी इनपुट लोअरकेस अक्षरों में हैं। उदाहरण के लिए, यदि हम फ़ंक्शन्स को निम्न तरह से कॉल करते हैं, तो हम आउटपुट देखेंगे
- Trie trie = new Trie()
- trie.insert("apple")
- trie.search("apple") // यह true लौटाएगा
- trie.search("app") // यह false लौटाएगा
- trie.startsWith("app") // यह true लौटाएगा
- trie.insert("app")
- trie.search("app") // यह true लौटाएगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- प्रारंभ में child नामक एक डिक्शनरी बनाएं।
- insert मेथड इस तरह होगा -
- current := child
- word में प्रत्येक अक्षर l के लिए -
- यदि l current में मौजूद नहीं है, तो current[l] := नई डिक्शनरी
- current := current[l]
- current[#] = 1
- search मेथड इस तरह होगा -
- current := child
- word में प्रत्येक अक्षर l के लिए -
- यदि l current में मौजूद नहीं है, तो false लौटाएं
- current := current[l]
- यदि current[#] = 1 तो true लौटाएं, अन्यथा false
- startsWith मेथड इस तरह होगा -
- current := child
- prefix में प्रत्येक अक्षर l के लिए -
- यदि l current में मौजूद नहीं है, तो false लौटाएं
- current := current[l]
- True लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
class Trie(object):
def __init__(self):
self.child = {}
def insert(self, word):
current = self.child
for l in word:
if l not in current:
current[l] = {}
current = current[l]
current['#'] = 1
def search(self, word):
current = self.child
for l in word:
if l not in current:
return False
current = current[l]
return '#' in current
def startsWith(self, prefix):
current = self.child
for l in prefix:
if l not in current:
return False
current = current[l]
return True
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app"))
इनपुट
ob1 = Trie() ob1.insert("apple") print(ob1.search("apple")) print(ob1.search("app")) print(ob1.startsWith("app")) ob1.insert("app") print(ob1.search("app"))
आउटपुट
True False True True
