मान लीजिए हमारे पास एक 2D बोर्ड और एक शब्द है, हमें यह ढूंढना है कि शब्द ग्रिड में मौजूद है या नहीं। शब्दों को क्रमिक रूप से आसन्न सेल के अक्षरों से बनाया जा सकता है, "आसन्न" सेल वे हैं जो क्षैतिज या लंबवत रूप से पड़ोसी सेल हैं। हमें एक ही अक्षर सेल का एक से अधिक बार उपयोग नहीं करना चाहिए। इसलिए यदि मैट्रिक्स इस तरह है -
| A | B | C | E |
| S | F | C | S |
| A | D | E | F |
दिए गए शब्द हैं "ABCCED", उत्तर true होगा, शब्द "SEE" के लिए, यह true होगा, लेकिन "ABCB" के लिए यह false होगा।
आइए चरण देखते हैं -
- हम इसे रिकर्सिव दृष्टिकोण का उपयोग करके हल करेंगे। इसलिए यदि रिकर्सिव मेथड का नाम find() है, यह मैट्रिक्स mat, शब्द, पंक्ति, कॉलम और इंडेक्स i लेता है। प्रारंभ में इंडेक्स i = 0
- यदि i = शब्द की लंबाई, तो True लौटाएं
- यदि पंक्ति >= mat की पंक्ति संख्या या पंक्ति < 0 या कॉलम >= mat की कॉलम संख्या या कॉलम < 0 या word[i], mat[row, col] के समान नहीं है, तो false लौटाएं
- mat[row, col] := "*"
- res := find(mat, word, row + 1, col, i + 1) या find(mat, word, row - 1, col, i + 1) या find(mat, word, row, col + 1, i + 1) या find(mat, word, row, col - 1, i + 1)
- mat[row, col] := word[i]
- res लौटाएं
- मुख्य कार्य इस तरह किया जाएगा -
- n := पंक्ति संख्या और m := कॉलम संख्या
- i को 0 से n तक की रेंज में
- j को 0 से m तक की रेंज में
- यदि word[0] = mat[i, j]
- यदि find(mat, word, i, j) false नहीं है, तो true लौटाएं
- यदि word[0] = mat[i, j]
- j को 0 से m तक की रेंज में
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
class Solution(object):
def exist(self, board, word):
n = len(board)
m = len(board[0])
for i in range(n):
for j in range(m):
if word[0] == board[i][j]:
if self.find(board, word, i, j):
return True
return False
def find(self, board, word, row, col, i=0):
if i == len(word):
return True
if row >= len(board) or row < 0 or col >= len(board[0]) or col < 0 or word[i] != board[row][col]:
return False
board[row][col] = '*'
res = self.find(board, word, row + 1, col, i + 1) or self.find(board, word, row - 1, col, i + 1) or self.find(board, word, row, col + 1, i + 1) or self.find(board, word, row, col - 1, i + 1)
board[row][col] = word[i]
return res
ob1 = Solution()
print(ob1.exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"))
इनपुट
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] "SEE"
आउटपुट
True