उपसर्ग खोज और Starts-With
ऐसी starts_with विधि जोड़िए जो दिए गए उपसर्ग से मेल खाने वाला कोई भी डाला गया शब्द होने पर true लौटाए, और इसका उपयोग स्वतः-पूर्णता सुझाव लागू करने में कीजिए।
उपसर्ग खोज और Starts-With, CoddyKit पर DSA Interview Prep का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। इस अध्ययन पथ के 3 तक कोई भी पाठ पूरा पढ़ना निःशुल्क है — इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ व्यावहारिक अभ्यास भी उपलब्ध कराता है। यह DSA Interview Prep सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
उपसर्ग वाले प्रश्नों की शक्ति
हैश मैप की तुलना में Trie का सबसे महत्वपूर्ण लाभ कुशल उपसर्ग-प्रश्न हैं। उपसर्ग वाला प्रश्न यह बताता है: ’इस उपसर्ग से कितने संग्रहीत शब्द शुरू होते हैं?’, ’इस उपसर्ग वाले सभी संग्रहीत शब्द कौन-से हैं?’ या केवल ’क्या इस उपसर्ग वाला कोई शब्द मौजूद है?’। ये प्रश्न O(p) में हल होते हैं, जहाँ p उपसर्ग की लंबाई है, और संग्रहीत शब्दों की कुल संख्या पर निर्भर नहीं करते — इसलिए Tries autocomplete और खोज-सुझाव के लिए आदर्श हैं।
starts_with विधि
starts_with(prefix) तब सत्य लौटाता है जब कोई संग्रहीत शब्द दिए गए उपसर्ग से शुरू होता है। उपसर्ग के प्रत्येक वर्ण का अनुसरण करते हुए Trie में आगे बढ़ें। यदि कोई किनारा गायब हुए बिना सभी वर्णों का अनुसरण किया जा सके, तो उपसर्ग मौजूद है और कम-से-कम एक शब्द उससे शुरू होता है। इसका कार्यान्वयन search जैसा ही है, अंतर केवल इतना है कि यात्रा पूरी होते ही हम सत्य लौटाते हैं — हम is_end की जाँच नहीं करते।
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # Falseautocomplete: उपसर्ग वाले सभी शब्द ढूँढना
autocomplete लागू करने के लिए उपसर्ग के अंतिम नोड तक जाएँ, फिर उस नोड से DFS (या BFS) चलाकर उससे निकलने वाली सभी शाखाओं के शब्द एकत्र करें। प्रत्येक एकत्रित प्रत्यय के आगे उपसर्ग जोड़कर पूरे शब्द फिर से बनाएँ। यह O(p + W) का संचालन है, जहाँ W सभी मेल खाने वाले शब्दों में वर्णों की कुल संख्या है।
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']क्रमबद्ध सुझाव लौटाना
क्रमबद्ध autocomplete के लिए DFS के दौरान children को वर्णमाला क्रम में देखें ( sorted(node.children.items()) पर पुनरावृत्ति करें)। चूँकि children शब्दकोश में संग्रहीत होते हैं, इससे O(ALPHABET_SIZE × depth) का अतिरिक्त खर्च आता है, लेकिन परिणाम शब्दकोशीय क्रम में मिलते हैं। सरणी-आधारित Trie में children हमेशा वर्णमाला क्रम में देखे जाते हैं, क्योंकि 0-25 के अनुक्रमांक क्रमबद्ध होते हैं।
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')आवृत्ति के आधार पर शीर्ष-k autocomplete सुझाव
आवृत्ति के आधार पर शीर्ष-k सुझावों के लिए प्रत्येक नोड में यह गिनती रखें कि वहाँ समाप्त होने वाले शब्द को कितनी बार search किया गया है। सुझाव एकत्र करते समय k आकार का अधिकतम-हीप उपयोग करें। इससे सभी मिलानों को सूची में बनाए बिना DFS के O(W) परिणाम-समुच्चय को O(k) तक घटाया जा सकता है। वास्तविक दुनिया के खोज इंजन तेज़ और प्रासंगिक सुझावों के लिए Trie में उपसर्ग की यात्रा को आवृत्ति डेटा के साथ जोड़ते हैं।
LeetCode 208 के लिए Trie लागू करना
LeetCode 208 ’Implement Trie (Prefix Tree)’ में ठीक यही माँगा गया है: insert(word), जोड़े गए शब्द का सटीक-मिलान बूलियन लौटाने वाला search(word), और उपसर्ग-मिलान बूलियन लौटाने वाला startsWith(prefix)। यह Trie का मानक कार्यान्वयन है। याद रखें: search के लिए is_end=True आवश्यक है; startsWith के लिए केवल उपसर्ग का पथ मौजूद होना आवश्यक है।
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # True’#’ को समाप्ति चिह्न के रूप में उपयोग करना (शब्दकोश Trie)
एक सुंदर संक्षिप्त उपाय Trie को नेस्टेड शब्दकोशों के रूप में संग्रहीत करना है, जिसमें शब्द के अंत को चिह्नित करने के लिए '#' जैसी विशेष sentinel कुंजी रखी जाती है। इससे TrieNode वर्ग की आवश्यकता समाप्त हो जाती है। यह स्पष्ट TrieNode ऑब्जेक्ट की तुलना में अधिक संक्षिप्त और इंटरव्यू के लिए सुविधाजनक है, लेकिन थोड़ा कम पठनीय है। दोनों कार्यान्वयन स्वीकार्य हैं; समय के दबाव में शब्दकोश वाला संस्करण जल्दी लिखा जा सकता है।
Trie का उपयोग करके सबसे लंबा साझा उपसर्ग
स्ट्रिंग की सूची का सबसे लंबा साझा उपसर्ग ढूँढने के लिए सभी स्ट्रिंग को Trie में insert करें और फिर मूल नोड से उस एकल पथ पर आगे बढ़ें जो तब तक मौजूद रहता है जब तक: (1) वर्तमान नोड की ठीक एक संतान हो, और (2) is_end असत्य हो। इनमें से कोई भी शर्त टूटते ही रुक जाएँ। अनुसरण किया गया पथ सबसे लंबा साझा उपसर्ग होता है।
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''शब्द प्रतिस्थापन समस्या
शब्द प्रतिस्थापन (LeetCode 648): मूल शब्दों का एक शब्दकोश और एक वाक्य दिए जाने पर, वाक्य के प्रत्येक शब्द को शब्दकोश में मिले सबसे छोटे मूल शब्द से बदलें। सभी मूल शब्दों को Trie में डालें। वाक्य के प्रत्येक शब्द के लिए Trie में तब तक आगे बढ़ें जब तक किसी मूल शब्द का अंत न मिल जाए — उस मूल शब्द को प्रतिस्थापन के रूप में लौटाएँ। यदि कोई मूल शब्द मेल न खाए, तो मूल शब्द ही रखें। इसकी जटिलता O(total chars) है, जबकि बलपूर्वक खोज में O(n × m) लगती है।
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))मैप योग युग्म समस्या
मैप योग (LeetCode 677): कुंजी-मान युग्म insert करें और दिए गए उपसर्ग वाली सभी कुंजियों के मानों का योग लौटाएँ। प्रत्येक TrieNode में val फ़ील्ड जोड़ें। insert के लिए अंत तक जाएँ और मान सेट करें; योग प्रश्नों के लिए उपसर्ग के अंतिम नोड तक जाएँ और उसके नीचे के सभी val फ़ील्ड का DFS द्वारा योग करें। वैकल्पिक रूप से, O(p) प्रश्नों के लिए insert के दौरान प्रत्येक नोड में संचयी योग संग्रहीत करें।
सीमित परिणामों वाली स्वतः-पूर्णता लागू करना
उत्पादन-स्तर की स्वतः-पूर्णता प्रणालियों में, जब हजारों शब्द किसी उपसर्ग से मेल खाते हों, तब सभी शब्द लौटाना अव्यावहारिक है। इसके बजाय, DFS भ्रमण के दौरान आकार k वाला अधिकतम-हीप उपयोग करें: अब तक मिले सर्वाधिक स्कोर वाले k शब्द बनाए रखें। यदि किसी DFS शाखा में शीर्ष-k शब्द होना संभव ही न हो, तो उस शाखा को समय से पहले रोक दें (स्कोर की ऊपरी सीमा के आधार पर छँटाई)। इससे k सुझावों के लिए प्रति प्रश्न O(p + k × log k) समय मिलता है — सभी मेल एकत्र करने की तुलना में बहुत बेहतर।
त्वरित जाँच
इस पाठ में शामिल डेटा संरचनाओं & एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी की अवधारणाओं के बारे में अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: उपसर्ग-जाँच उपसर्ग-पथ पर चलती है और उसके मौजूद होने पर सत्य लौटाती है — is_end की जाँच आवश्यक नहीं होती, स्वतः-पूर्णता में DFS उपसर्ग के अंतिम नोड से सभी शब्द एकत्र करता है और नीचे जाते समय वर्ण जोड़ता है, और नोड्स में गणनाएँ या मान जोड़ने से योग संबंधी प्रश्नों और शीर्ष-k सुझावों को सक्षम किया जा सकता है। अगले पाठ में हम ट्राई में वाइल्डकार्ड और नियमित-अभिव्यक्ति मिलान जोड़ेंगे।
एआई शिक्षक के साथ Python सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 30
- पाठ
- 120
अक्सर पूछे जाने वाले प्रश्न
क्या “उपसर्ग खोज और Starts-With” पाठ निःशुल्क है?
हाँ — DSA Interview Prep अध्ययन पथ के 3 तक कोई भी पाठ, जिसमें “उपसर्ग खोज और Starts-With” भी शामिल है, यहाँ वेब पर पूरा पढ़ना निःशुल्क है। इसके बाद CoddyKit PRO हर पाठ अनलॉक करता है, साथ ही अंतर्निर्मित कोड संपादक और चौबीसों घंटे एआई शिक्षक के साथ इंटरैक्टिव अभ्यास भी उपलब्ध कराता है। DSA Interview Prep पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“उपसर्ग खोज और Starts-With” में मैं क्या सीखूँगा?
ऐसी starts_with विधि जोड़िए जो दिए गए उपसर्ग से मेल खाने वाला कोई भी डाला गया शब्द होने पर true लौटाए, और इसका उपयोग स्वतः-पूर्णता सुझाव लागू करने में कीजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ DSA Interview Prep का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या DSA Interview Prep शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर DSA Interview Prep शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।
“उपसर्ग खोज और Starts-With” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस DSA Interview Prep पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर DSA Interview Prep पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- TrieNode क्लास: प्रविष्टि और खोज
- उपसर्ग खोज और Starts-With
- Trie में वाइल्डकार्ड और Regex खोज
- Word Search II: ग्रिड पर Trie + बैकट्रैकिंग