পাইথনে Word Search (শব্দ খুঁজে বের করা)

মান করুন একটি ২D বোর্ড এবং একটি শব্দ আছে, আমাদের খুঁজে বের করতে হবে শব্দটি গ্রিডে আছে কিনা। শব্দগুলো আঁকা যায় সিকোয়েনশিয়ালি অ্যাডজেসেন্ট সেলের লেটার থেকে, "অ্যাডজেসেন্ট" সেল মানে হরিজন্টালি বা ভার্টিক্যালি নighbouring সেল। একই লেটার সেল একবারের বেশি ব্যবহার করা যাবে না। ম্যাট্রিক্স যদি নিচের মতো হয়:

দেয়া শব্দ "ABCCED" হলে উত্তর সত্য, "SEE" হলে সত্য, কিন্তু "ABCB" হলে মিথ্যা।

ধাপগুলো (রিকারসিভ ব্যাকট্র্যাকিং):

• রিকারসিভ পদ্ধতিতে সমাধান করব। মেথডের নাম find(), যা নিবে ম্যাট্রিক্স mat, শব্দ word, রো row, কলাম col এবং ইনডেক্স i। প্রাথমিকভাবে i = 0
• যদি i == len(word), তবে সত্য রিটার্ন করুন
• যদি row >= mat-এর সারি সংখ্যা বা row < 0 বা col >= mat-এর কলাম সংখ্যা বা col < 0 বা word[i] != mat[row][col], তবে মিথ্যা রিটার্ন করুন
• mat[row][col] := "*" (ভিজিটেড মার্ক)
• res := find(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) or find(mat, word, row, col-1, i+1)
• mat[row][col] := word[i] (ব্যাকট্র্যাক)
• res রিটার্ন করুন
• মেইন টাস্ক:
  • n := সারি সংখ্যা, m := কলাম সংখ্যা
  • i ০ থেকে n পর্যন্ত
    • j ০ থেকে m পর্যন্ত
      • যদি 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