পাইথনে অক্ষরের ম্যাট্রিক্স থেকে তৈরি করা যাওয়া শব্দের সংখ্যা গণনা করার প্রোগ্রাম

মনে করুন আমাদের একটি 4x4 অক্ষরের বোর্ড এবং একটি শব্দের তালিকা আছে, আমাদের বোর্ডে উপস্থিত শব্দের সর্বোচ্চ সংখ্যা খুঁজে বের করতে হবে যা সম্মিলিত অক্ষরের একটি সিকোয়েন্স দিয়ে তৈরি করা যায়, প্রতিটি শব্দের জন্য একটি সেল বেশি একবার ব্যবহার করা যাবে না (কিন্তু অন্য শব্দের জন্য সেল পুনরায় ব্যবহার করা যায়)। আমরা উপরে, নিচে, বামে, ডানে বা ডায়াগোনাল দিকে যেতে পারি।

উদাহরণস্বরূপ, যদি ইনপুট হয়

m	b	f	d
x	a	y	a
t	z	t	r
s	q	q	q

words = ["bat", "far", "mat"], তবে আউটপুট হবে 3, কারণ আমরা mat [0,1] → [1,1] → [2,0], bat [0,2] → [1,1] → [2,2], এবং far [0,2] → [1,3] → [2,3] তৈরি করতে পারি।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

N := A-এর সারি সংখ্যা, M := A-এর কলাম সংখ্যা
trie := একটি নতুন ম্যাপ
words-এ প্রতিটি শব্দের জন্য, করুন
- current := trie
- শব্দের প্রতিটি c-এর জন্য, করুন
  - যদি c current-এ থাকে, তবে
    - current := current[c]
  - অন্যথায়,
    - current[c] := একটি নতুন ম্যাপ
    - current := current[c]
- current["*"] := True
ans := 0
একটি dfs() ফাংশন সংজ্ঞায়িত করুন। এটি x, y, d নিবে
যদি "*" d-এ থাকে, তবে
- d["*"] মুছুন
- ans := ans + 1
temp := A[x, y]
A[x, y] := "#"
[x-1, x, x+1]-এ প্রতিটি আইটেম i-এর জন্য, করুন
- [y-1, y, y+1]-এ প্রতিটি আইটেম j-এর জন্য, করুন
  - যদি i এবং j ম্যাট্রিক্সের পরিসরে থাকে এবং A[i, j] d-এ থাকে, তবে
    - dfs(i, j, d[A[i, j]])
A[x, y] := temp
মূল মেথড থেকে নিচের কাজগুলো করুন
i = 0 থেকে N পর্যন্ত, করুন
- j = 0 থেকে M পর্যন্ত, করুন
  - যদি A[i][j] trie-এ থাকে, তবে
    - dfs(i, j, trie[A[i, j]])
ans রিটার্ন করুন

উদাহরণ (পাইথন)

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

class Solution:    def solve(self, A, words):       N = len(A)       M = len(A[0])       trie = dict()       for word in words:          current = trie          for c in word:             if c in current:                current = current[c]             else:                current[c] = dict()                current = current[c]          current["*"] = True       ans = 0       def dfs(x, y, d):          nonlocal ans          if "*" in d:             del d["*"]             ans += 1          temp = A[x][y]          A[x][y] = "#"          for i in [x - 1, x, x + 1]:             for j in [y - 1, y, y + 1]:                if 0 <= i < N and 0 <= j < M and A[i][j] in d: dfs(i, j, d[A[i][j]])          A[x][y] = temp       for i in range(N):          for j in range(M):             if A[i][j] in trie:                dfs(i, j, trie[A[i][j]])       return ans ob = Solution() matrix = [    ["m", "b", "f", "d"],    ["x", "a", "y", "a"],    ["t", "z", "t", "r"],    ["s", "q", "q", "q"] ] words = ["bat", "far", "mat"] print(ob.solve(matrix, words))

ইনপুট

[ ["m", "b", "f", "d"], ["x", "a", "y", "a"], ["t", "z", "t", "r"], ["s", "q", "q", "q"] ], ["bat", "far", "mat"]