मान लीजिए हमारे पास एक 2D बोर्ड और शब्दों की एक सूची है। तो शब्दकोश से, हमें बोर्ड में सभी शब्द खोजने हैं। यहां प्रत्येक शब्द को क्रमिक रूप से आसन्न कोशिका के अक्षरों से बनाया जाना चाहिए, जहां आसन्न कोशिकाएं क्षैतिज या लंबवत रूप से पड़ोसी होती हैं। हमें ध्यान रखना होगा कि वही अक्षर कोशिका एक शब्द में एक से अधिक बार उपयोग नहीं की जा सकती।
इसलिए यदि इनपुट इस तरह है −
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
एक सरणी result बनाएं
solve() नामक एक विधि परिभाषित करें, यह board, d, i, j s लेगा
जब i या j बोर्ड की पंक्ति और कॉलम सीमा में नहीं हैं, तो false लौटाएं
l := board[i, j]
यदि l d में मौजूद है, तो
d := d[l], s के साथ l जोड़ें
यदि # d में है और d[#] null नहीं है, तो
s को result में डालें
d[#] := 0 सेट करें
board[i, j] := *
यदि i+1 < बोर्ड में पंक्तियों की संख्या और board[i + 1, j] d में है, तो
solve(board, d, i + 1, j, s) कॉल करें
यदि j+1 < बोर्ड में कॉलम की संख्या और board[i, j+1] d में है, तो
solve(board, d, i, j+1, s) कॉल करें
यदि i-1 > 0 और board[i - 1, j] d में है, तो
solve(board, d, i - 1, j, s) कॉल करें
यदि j-1 > 0 और board[i, j-1] d में है, तो
solve(board, d, i, j-1, s) कॉल करें
board[i, j] := l
insert() नामक एक विधि परिभाषित करें, यह word और डिक्शनरी t लेगा
current := t
word में i के लिए
यदि i current में नहीं है, तो current[i] := नया मैप
current := current[i]
current[#] := 1
मुख्य विधि से निम्नलिखित करें −
एक मैप t बनाएं
words में प्रत्येक word के लिए: insert(word, t) कॉल करें
बोर्ड में प्रत्येक कोशिका i, j के लिए − solve(board, t, i, j) कॉल करें
result लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
class Solution(object): def findWords(self, board, words): self.result = [] t = {} for word in words: self.insert(word,t) for i in range(len(board)): for j in range(len(board[0])): self.solve(board,t,i,j) return self.result def solve(self,board,d,i,j,s=""): if i<0 or j<0 or i>=len(board) or j>=(len(board[0])): return l = board[i][j] if l in d: d = d[l] s+=l if "#" in d and d['#']: self.result.append(s) d['#'] = 0 board[i][j] = '*' if i+1=0 and board[i-1][j] in d : self.solve(board,d,i-1,j,s) if j-1>=0 and board[i][j-1] in d : self.solve(board,d,i,j-1,s) board[i][j] = l def insert(self, word,t): current = t for i in word: if i not in current: current[i] = {} current =current[i] current['#']=1 ob = Solution() print(ob.findWords([["o","a","a","n"],["e","t","e","a"],["i","h","k", "r"],["i","f","l","v"]],["oath","pea","tea","rain"])) इनपुट
[["o","a","a","n"], ["e","t","e","a"], ["i","h","k","r"], ["i","f","l","v"]], ["oath","pea","tea","rain"]
आउटपुट
['oath', 'tea']
