पायथन में वर्ड सर्च II

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

तो अगर इनपुट की तरह है -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक सरणी परिणाम बनाएं

• हल () नामक एक विधि को परिभाषित करें, यह बोर्ड, d, i, j s

  . लेगा

• जब या तो i या j क्रमशः बोर्ड पंक्ति और स्तंभ श्रेणी में न हों, तो झूठी वापसी करें

• एल :=बोर्ड[i, j]

• अगर l d में मौजूद है, तो

  • d :=d[l], l को s से जोड़ना

  • यदि # d में है और d[#] शून्य नहीं है, तो

    • परिणाम में s डालें

    • सेट डी [#] :=0

  • बोर्ड [i, j] :=*

  • अगर i+1 <बोर्ड और बोर्ड में पंक्तियों की संख्या [i + 1, j] d में, तो

    • कॉल सॉल्व (बोर्ड, डी, आई + 1, जे, एस)

  • यदि j+1 <बोर्ड और बोर्ड में स्तंभों की संख्या[i, j+1] d में, तो

    • कॉल सॉल्व (बोर्ड, डी, आई, जे+1, एस)

  • अगर i-1> 0 और बोर्ड[i-1, j] d में, तो

    • कॉल सॉल्व (बोर्ड, डी, आई -1, जे, एस)

  • अगर j-1> 0 और बोर्ड[i, j-1] d में है, तो

    • कॉल सॉल्व (बोर्ड, डी, आई, जे-1, एस)

  • बोर्ड[i, j] :=l

• इंसर्ट () नामक एक विधि को परिभाषित करें, यह शब्द और शब्दकोश टी लेगा

• वर्तमान:=टी

• मेरे लिए शब्द में

  • अगर मैं वर्तमान में नहीं हूं, तो वर्तमान [i]:=नया नक्शा

  • वर्तमान:=वर्तमान [i]

• वर्तमान [#] :=1

• मुख्य विधि से निम्न कार्य करें -

• एक नक्शा बनाएं टी

• शब्दों में शब्द के लिए:कॉल सम्मिलित करें (शब्द, टी)

• बोर्ड में प्रत्येक सेल i, j के लिए - कॉल सॉल्व (बोर्ड, टी, आई, जे)

• वापसी परिणाम

उदाहरण

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

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<len(board) and board[i+1][j] in d :
            self.solve(board,d,i+1,j,s)
         if j+1 < len(board[0]) and board[i][j+1] in d:
            self.solve(board,d,i,j+1,s)
         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']