পাইথনে শব্দ অনুসন্ধান II

ধরুন আমাদের একটি 2D বোর্ড এবং শব্দের একটি তালিকা আছে। তাই অভিধান থেকে বোর্ডের সব শব্দ খুঁজে বের করতে হবে। এখানে প্রতিটি শব্দকে ক্রমানুসারে সংলগ্ন কক্ষের অক্ষর থেকে তৈরি করতে হবে, যেখানে সংলগ্ন কোষগুলি অনুভূমিকভাবে বা উল্লম্বভাবে প্রতিবেশী। আমাদের মনে রাখতে হবে যে একই অক্ষর ঘর একটি শব্দে একবারের বেশি ব্যবহার করা যাবে না।

তাই যদি ইনপুট −

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি অ্যারে ফলাফল তৈরি করুন

• সমাধান() নামক একটি পদ্ধতির সংজ্ঞা দিন, এটি বোর্ড, d, i, j s

  লাগবে

• যখন i বা j যথাক্রমে বোর্ড সারি এবং কলাম পরিসরে না থাকে, তখন মিথ্যা ফেরত দিন

• l :=বোর্ড[i, j]

• যদি d-এ l উপস্থিত থাকে, তাহলে

  • d :=d[l], s এর সাথে l সংযুক্ত করুন

  • যদি # d-এ থাকে এবং d[#] শূন্য না হয়, তাহলে

    • ফলাফলে s ঢোকান

    • সেট d[#] :=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, জে, এস)

  • যদি d-এ j-1> 0 এবং বোর্ড[i, j-1] হয়, তাহলে

    • কল সল্ভ (বোর্ড, ডি, আই, জে-১, এস)

  • বোর্ড[i, j] :=l

• insert() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি শব্দ এবং অভিধান টি

  নেবে

• বর্তমান :=t

• আমি শব্দে

  • যদি আমি কারেন্টে না থাকি, তাহলে বর্তমান[i] :=নতুন মানচিত্র

  • বর্তমান :=বর্তমান[i]

• বর্তমান [#] :=1

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• একটি মানচিত্র তৈরি করুন t

• শব্দে শব্দের জন্য:insert(word, t)

  কল করুন

• প্রতিটি কক্ষের জন্য i, j বোর্ডে − কল সল্ভ (বোর্ড, t, 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']