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

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

প্রদত্ত শব্দগুলি "ABCCED" বলে, উত্তরটি সত্য হবে, "দেখুন" শব্দের জন্য, এটি সত্য হবে, তবে "ABCB" এর জন্য যদি মিথ্যা হয়।

আসুন ধাপগুলো দেখি -

• আমরা পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করে এটি সমাধান করব। তাই যদি পুনরাবৃত্ত পদ্ধতির নাম বলা হয় find(), এটি ম্যাট্রিক্স ম্যাট, শব্দ, সারি, কল এবং সূচক i লাগে। প্রাথমিকভাবে সূচক i =0
• যদি i =শব্দের দৈর্ঘ্য, তাহলে সত্য ফেরত দিন
• যদি সারি>=ম্যাট বা সারির সারি গণনা <0 বা col>=ম্যাট বা কল <0 বা শব্দ[i] ম্যাট[row, col] এর মতো না হয়, তাহলে মিথ্যা ফেরত দিন
• mat[সারি, কল] :=“*”
• res :=খুঁজুন(mat, word, row + 1, col, i + 1) or find(mat, word, row - 1, col, i + 1) or find(mat, word, row, col + 1, i + 1) অথবা খুঁজুন(mat, word, row, col - 1, i + 1)
• mat[সারি, কল] :=শব্দ[i]
• রিটার্ন রিটার্ন
• মূল কাজটি −
এর মত করা হবে
• n :=সারি গণনা এবং m :=কলাম গণনা
• আমি 0 থেকে n
  পরিসরে 0 থেকে m
  পরিসরে j-এর জন্য
  • if word[0] =mat[i, j]
    • যদি find(mat, word, 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