Word Search II: ग्रिड पर Trie + बैकट्रैकिंग
सभी लक्षित शब्दों को Trie में डालिए और 2D बोर्ड पर DFS बैकट्रैकिंग चलाकर O(m × n × 4^L) में सभी मान्य शब्द एक साथ खोजिए।
Word Search II: ग्रिड पर Trie + बैकट्रैकिंग, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 4वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
वर्ड सर्च II की समस्या
वर्ड सर्च II (LeetCode 212): वर्णों के m × n बोर्ड और शब्दों की सूची को देखते हुए, वे सभी शब्द खोजें जो क्रमिक रूप से आसन्न कक्षों (क्षैतिज या ऊर्ध्वाधर) से बनाए जा सकते हैं, जहाँ प्रत्येक कक्ष का उपयोग केवल एक बार किया जा सकता है। यह वर्ड सर्च I (एकल शब्द) से कठिन है, क्योंकि हमें सभी मेल खाने वाले शब्द एक साथ खोजने हैं — प्रत्येक शब्द के लिए सरल तरीके से वर्ड सर्च I चलाने की जटिलता O(W × m × n × 4^L) होगी, जो बहुत धीमी है।
ट्राई और बैकट्रैकिंग का उपयोग क्यों करें
सभी लक्षित शब्दों को एक ट्राई में सम्मिलित करके और फिर बोर्ड पर DFS बैकट्रैकिंग चलाकर हम सभी शब्दों को एक साथ खोज सकते हैं। प्रत्येक बोर्ड कक्ष पर यह जाँचने के बजाय कि ‘क्या यह पथ मेरे लक्षित शब्द को बनाता है?’, हम जाँचते हैं कि ‘क्या यह पथ ट्राई के किसी उपसर्ग से मेल खाता है?’ जैसे ही कोई ट्राई उपसर्ग विफल होता है, हम पूरी DFS शाखा की छँटाई कर देते हैं — इससे समान उपसर्ग साझा करने वाले सभी शब्दों के लिए दोहराया हुआ काम बच जाता है।
शब्द-सूची से ट्राई बनाना
सभी शब्दों को ट्राई में सम्मिलित करें। केवल बूलियन मान रखने के बजाय पूरा शब्द पत्ती नोड में (node.word में) रखें, ताकि बैकट्रैकिंग के दौरान पूरा मिलान मिलने पर हम शब्द को वर्ण-दर-वर्ण दोबारा बनाए बिना तुरंत परिणामों में जोड़ सकें।
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(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.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')ग्रिड पर DFS बैकट्रैकिंग
बोर्ड के प्रत्येक कक्ष से DFS शुरू करें। प्रत्येक चरण में: (1) जाँचें कि वर्तमान कक्ष का वर्ण वर्तमान ट्राई नोड में किसी संतति के रूप में मौजूद है या नहीं; (2) यदि हाँ, तो कक्ष को देखा हुआ चिह्नित करें (उसे '#' जैसे संकेतक से बदलें), 4 पड़ोसी कक्षों में पुनरावृत्ति करें; (3) पुनरावृत्ति के बाद कक्ष को पहले के मान पर पुनर्स्थापित करें (चिह्न हटाएँ)। जब किसी ट्राई नोड में रिक्त से भिन्न word हो, तो उसे परिणामों में जोड़ें और पुनरावृत्तियों से बचने के लिए उसे None पर सेट करें।
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, 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.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']जटिलता विश्लेषण
समय: O(m × n × 4^L), जहाँ L अधिकतम शब्द-लंबाई है। m×n प्रारंभिक कक्षों में से प्रत्येक के लिए DFS अधिकतम 4^L पथों का अन्वेषण करता है। ट्राई उन पथों की छँटाई कर देता है जो किसी शब्द के उपसर्ग से मेल नहीं खाते, इसलिए व्यवहार में यह बहुत तेज़ होता है। ट्राई बनाना O(W × L) है, जहाँ W शब्दों की संख्या है। स्थान: ट्राई के लिए O(W × L), साथ में पुनरावृत्ति-स्टैक की गहराई के लिए O(L)।
छँटाई: शब्द मिलने के बाद पत्ती नोड हटाना
किसी शब्द को खोज लेने के बाद, यदि उसके पास कोई संतति नहीं है, तो केवल शब्द को रिक्त करने के बजाय पत्ती नोड को ट्राई से हटा दें। इससे बाद की DFS कॉल में निष्प्राण शाखाओं पर दोबारा जाने से बचा जाता है। जब शब्द मिलने के बाद किसी नोड की संततियाँ खाली हो जाएँ, तो उसे उसके अभिभावक की संतति-शब्दकोश से हटा दें। यह अनुकूलन तब महत्वपूर्ण होता है जब कई शब्द लंबे उपसर्ग साझा करते हों।
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')नोड में word रखना बेहतर क्यों है
ट्राई की पत्ती में पूरा शब्द रखना (DFS पथ से उसे दोबारा बनाने के बजाय) दो लाभ देता है: (1) मिलान मिलने पर O(1) में शब्द प्राप्त हो जाता है, जबकि पथ को दोबारा बनाने में O(L) लगता है; (2) शब्द मिलने के बाद node.word = None करना अलग परिणाम-समुच्चय की आवश्यकता के बिना साफ़-सुथरा, O(1) पुनरावृत्ति-निवारण है। खासकर वर्ड सर्च II में पुनरावृत्तियों को रोकना महत्वपूर्ण है, क्योंकि सैद्धांतिक रूप से एक ही शब्द अलग-अलग पथों से मिल सकता है।
देखे गए कक्षों को उसी स्थान पर चिह्नित करना
अलग visited समुच्चय का उपयोग करने के बजाय (जिसमें प्रत्येक DFS पथ के लिए O(m × n) स्थान चाहिए), हम कक्ष के वर्ण को '#' जैसे संकेतक से बदलकर उसी स्थान पर चिह्नित करते हैं। DFS लौटने के बाद मूल वर्ण पुनर्स्थापित कर दें। इस तकनीक से: (1) प्रत्येक कक्ष के लिए O(1) अतिरिक्त स्थान लगता है; (2) एक ही पथ में दोबारा जाने से अपने-आप बचाव होता है; (3) ट्राई भ्रमण पर कोई प्रभाव नहीं पड़ता, क्योंकि '#' ट्राई में कभी मौजूद नहीं होगा।
संभालने योग्य विशेष स्थितियाँ
महत्वपूर्ण विशेष स्थितियाँ: (1) शब्द-सूची में दोहराए गए शब्द — उन्हें किसी समुच्चय में रखें या परिणामों में पुनरावृत्तियों को रोकने के लिए node.word = None वाली तरकीब अपनाएँ; (2) बोर्ड के आयामों से अधिक लंबे शब्द — उन्हें बनाया नहीं जा सकता, लेकिन आसन्न कक्ष समाप्त हो जाने पर DFS स्वाभाविक रूप से रुक जाता है; (3) एक-कक्ष वाला बोर्ड — केवल एक-वर्ण वाले शब्द मिल सकते हैं; (4) अलग-अलग पथों से मिलने योग्य एक ही शब्द — node.word = None वाली तरकीब दोहरी गिनती रोकती है।
सरल तरीके से तुलना
सरल तरीका: W शब्दों में से प्रत्येक के लिए वर्ड सर्च I चलाएँ: O(W × m × n × 4^L)। ट्राई के साथ सभी शब्द एक साथ खोजे जाते हैं: W से स्वतंत्र होकर O(m × n × 4^L)। 10 लंबाई वाले W=1000 शब्दों के लिए 10×10 बोर्ड पर सरल तरीका ट्राई से 1000 गुना धीमा है। ट्राई साझा उपसर्ग फ़िल्टर की तरह काम करता है, जो सभी शब्दों में लागत को बाँट देता है — यह बड़े-स्तरीय सुधार के लिए डेटा संरचना के उपयोग का उत्कृष्ट उदाहरण है।
पूर्ण समाधान का सारांश
वर्ड सर्च II का पूर्ण समाधान: शब्दों के साथ ट्राई बनाएँ और पत्ती में शब्द-शृंखला रखें। प्रत्येक बोर्ड कक्ष के लिए DFS चलाएँ: जाँचें कि वर्तमान वर्ण वर्तमान ट्राई नोड में मौजूद है या नहीं, कक्ष को '#' चिह्नित करें, 4 पड़ोसी कक्षों में पुनरावृत्ति करें और कक्ष को पुनर्स्थापित करें। जब node.word शून्येतर हो, तो उसे परिणामों में जोड़ें और उसे रिक्त कर दें। उपयोग के बाद खाली ट्राई शाखाओं की वैकल्पिक रूप से छँटाई करें। परिणामों की सूची लौटाएँ। समय: O(m×n×4^L), स्थान: O(W×L) ट्राई + O(L) पुनरावृत्ति।
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resultत्वरित जाँच
इस पाठ में शामिल डेटा संरचनाओं & एल्गोरिदम — कोडिंग साक्षात्कार की तैयारी की अवधारणाओं के बारे में अपनी समझ जाँचें।
पाठ का पुनरावलोकन
इस पाठ में आपने सीखा: वर्ड सर्च II साझा उपसर्ग की छँटाई के साथ एक साथ कई शब्दों की खोज संभव बनाने के लिए ट्राई का उपयोग करता है, ट्राई की पत्ती में शब्द-शृंखला रखने से O(1) में शब्द प्राप्त होता है और उसे मिलने के बाद रिक्त करके आसानी से पुनरावृत्तियाँ हटाई जा सकती हैं, और '#' के साथ उसी स्थान पर देखा हुआ चिह्नित करने से प्रत्येक DFS पथ के लिए O(m×n) अतिरिक्त स्थान की आवश्यकता नहीं रहती। इससे ट्राई और स्ट्रिंग एल्गोरिदम का पाठ्यक्रम पूरा होता है — आपने साक्षात्कारों में उपयोग होने वाली सबसे शक्तिशाली स्ट्रिंग-विशिष्ट डेटा संरचनाओं में से एक पर अच्छी पकड़ बना ली है।
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “Word Search II: ग्रिड पर Trie + बैकट्रैकिंग” पाठ निःशुल्क है?
हाँ—“Word Search II: ग्रिड पर Trie + बैकट्रैकिंग” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“Word Search II: ग्रिड पर Trie + बैकट्रैकिंग” में मैं क्या सीखूँगा?
सभी लक्षित शब्दों को Trie में डालिए और 2D बोर्ड पर DFS बैकट्रैकिंग चलाकर O(m × n × 4^L) में सभी मान्य शब्द एक साथ खोजिए। आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 4वाँ पाठ है।
“Word Search II: ग्रिड पर Trie + बैकट्रैकिंग” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- TrieNode क्लास: प्रविष्टि और खोज
- उपसर्ग खोज और Starts-With
- Trie में वाइल्डकार्ड और Regex खोज
- Word Search II: ग्रिड पर Trie + बैकट्रैकिंग