पायथन में शब्द खोज

मान लीजिए हमारे पास एक 2डी बोर्ड और एक शब्द है, हमें यह पता लगाना है कि शब्द ग्रिड में मौजूद है या नहीं। शब्द क्रमिक रूप से आसन्न सेल के अक्षरों से बनाए जा सकते हैं, "आसन्न" कोशिकाएँ क्षैतिज या लंबवत पड़ोसी कोशिकाएँ होती हैं। हमें एक ही लेटर सेल को एक से ज्यादा बार इस्तेमाल नहीं करना चाहिए। तो अगर मैट्रिक्स की तरह है -

दिए गए शब्दों को "ABCCED" कहते हैं, उत्तर सत्य होगा, शब्द "SEE" के लिए यह सत्य होगा, लेकिन "ABCB" के लिए यदि गलत होगा।

आइए चरणों को देखें -

• हम इसे पुनरावर्ती दृष्टिकोण का उपयोग करके हल करेंगे। इसलिए यदि पुनरावर्ती विधि नाम को खोज () कहा जाता है, तो यह मैट्रिक्स मैट, शब्द, पंक्ति, कॉल और इंडेक्स i लेता है। प्रारंभ में सूचकांक i =0
• यदि i =शब्दों की लंबाई, तो सही लौटें
• यदि पंक्ति>=चटाई या पंक्ति की पंक्ति संख्या <0 या col>=चटाई या स्तंभ की पंक्ति संख्या <0 या शब्द[i] चटाई के समान नहीं है [पंक्ति, col], तो झूठी वापसी करें
• mat[row, col] :="*"
• res:=ढूंढें (चटाई, शब्द, पंक्ति + 1, कॉलम, i + 1) या ढूंढें (चटाई, शब्द, पंक्ति -1, कॉलम, i + 1) या ढूंढें (चटाई, शब्द, पंक्ति, कॉलम + 1, i + 1) या ढूंढें (चटाई, शब्द, पंक्ति, कॉलम -1, i + 1)
• mat[row, col] :=word[i]
• रिटर्न रेस
• मुख्य कार्य इस तरह किया जाएगा -
• n :=पंक्ति गणना और m :=स्तंभ गणना
• मैं के लिए 0 से n की सीमा में
  • जे के लिए 0 से मी की सीमा में
    • यदि शब्द[0] =चटाई[i, j]
      • अगर ढूंढें (चटाई, शब्द, i, j) गलत नहीं है, तो सही लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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