पायथन में अक्षरों के मैट्रिक्स से उत्पन्न होने वाले शब्दों की संख्या की गणना करने का कार्यक्रम

मान लीजिए कि हमारे पास अक्षरों का 4 x 4 बोर्ड और शब्दों की एक सूची है, हमें शब्दों की सबसे बड़ी संख्या को खोजना है जो बोर्ड में आसन्न अक्षरों के अनुक्रम द्वारा उत्पन्न किया जा सकता है, एक सेल का उपयोग करके प्रति शब्द अधिकतम एक बार (लेकिन हम दूसरे शब्दों के लिए कोशिकाओं का पुन:उपयोग कर सकते हैं)। हम ऊपर, नीचे, बाएँ, दाएँ, या विकर्ण दिशा में जा सकते हैं।

तो, अगर इनपुट पसंद है

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

शब्द =["बैट", "दूर", "मैट"], तो आउटपुट 3 होगा, क्योंकि हम मैट [0,1] → [1,1] → [2,0], बैट [0,] उत्पन्न कर सकते हैं। 2] → [1,1] → [2,2], और दूर [0,2] → [1,3] → [2,3]।

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

N:=A, M की पंक्ति गणना:=A के आकार की स्तंभ गणना
ट्राई :=एक नया नक्शा
शब्दों में प्रत्येक शब्द के लिए, करें
- वर्तमान:=ट्राई
- शब्द में प्रत्येक सी के लिए, करें
  - अगर c करंट में है, तो
    - वर्तमान:=वर्तमान [सी]
  - अन्यथा,
    - वर्तमान [c] :=एक नया नक्शा
    - वर्तमान:=वर्तमान [सी]
- वर्तमान ["*"] :=सच
उत्तर :=0
फ़ंक्शन को परिभाषित करें dfs() । इसमें x, y, d लगेगा
अगर "*" d में है, तो
- d["*"]
  remove हटाएं
- उत्तर:=उत्तर + 1
अस्थायी:=ए[एक्स, वाई]
ए[एक्स, वाई] :="#"
[x - 1, x, x + 1] में प्रत्येक आइटम के लिए, करें
- [y - 1, y, y + 1] में प्रत्येक आइटम j के लिए, करें
  - यदि i और j मैट्रिक्स की श्रेणी में हैं और A[i, j] d में है, तो
    - dfs(i, j, d[A[i, j]])
ए [एक्स, वाई]:=अस्थायी
मुख्य विधि से निम्न कार्य करें -
मेरे लिए 0 से N की सीमा में, करें
- j के लिए 0 से M की सीमा में, करें
  - अगर A[i][j] ट्राई में है, तो
    - dfs(i, j, trie[A[i, j]])
वापसी उत्तर

उदाहरण (पायथन)

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

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"]