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

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

उदाहरण के लिए, दिए गए बोर्ड और words = ["bat", "far", "mat"] के लिए आउटपुट 3 होगा।

एल्गोरिदम (ट्राई + DFS)

शब्दों से trie बनाएं
ans := 0
dfs(x, y, d) फ़ंक्शन परिभाषित करें:
- यदि "*" in d (शब्द का अंत), तो ans++, del d["*"]
- temp := A[x][y], A[x][y] = "#" (विज़िटेड मार्क करें)
- 8 दिशाओं में पड़ोसियों के लिए, यदि वैध और A[i][j] in d, तो dfs(i, j, d[A[i][j]]) कॉल करें
- A[x][y] = temp (बैकट्रैक)
प्रत्येक सेल (i, j) के लिए, यदि A[i][j] in trie, तो dfs(i, j, trie[A[i][j]]) कॉल करें
ans वापस करें

उदाहरण

class Solution:
    def solve(self, A, words):
        N, M = len(A), len(A[0])
        trie = {}
        for word in words:
            cur = trie
            for c in word:
                cur = cur.setdefault(c, {})
            cur["*"] = 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"]