मैंने कुछ समान समाधानों को डिबग किया है, लेकिन सोच रहा है कि क्या हम आंशिक मिलान उपसर्ग (ट्री ट्री की खोज विधि में) ट्री ट्री को बेहतर बना सकते हैं, वर्तमान खोज विधि केवल जांचें कि एक पूर्ण शब्द मेल खाता है या नहीं नहीं) प्रदर्शन में सुधार करने के लिए, जो पहले गलत रास्ते से वापस आ सकता है? मुझे इस विचार के लिए बहुत आश्वस्त नहीं है, इसलिए पहले सलाह की तलाश करें।शब्द खोज में ट्री ट्री मैच प्रदर्शन
मैं इसी तरह के समाधानों में से एक पोस्ट करता हूं। धन्यवाद।
2 डी बोर्ड और शब्दकोश से शब्दों की एक सूची को देखते हुए, बोर्ड में सभी शब्द खोजें।
प्रत्येक शब्द अनुक्रमिक रूप से आसन्न सेल के अक्षरों से बनाया जाना चाहिए, जहां "आसन्न" कोशिकाएं क्षैतिज या लंबवत पड़ोसी हैं। एक ही अक्षर कक्ष का प्रयोग किसी शब्द में एक से अधिक बार नहीं किया जा सकता है।
उदाहरण के लिए, को देखते हुए शब्द = ["oath","pea","eat","rain"] और बोर्ड =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
वापसी [ "खाने", "शपथ"]
class TrieNode():
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.isWord = False
class Trie():
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for w in word:
node = node.children[w]
node.isWord = True
def search(self, word):
node = self.root
for w in word:
node = node.children.get(w)
if not node:
return False
return node.isWord
class Solution(object):
def findWords(self, board, words):
res = []
trie = Trie()
node = trie.root
for w in words:
trie.insert(w)
for i in xrange(len(board)):
for j in xrange(len(board[0])):
self.dfs(board, node, i, j, "", res)
return res
def dfs(self, board, node, i, j, path, res):
if node.isWord:
res.append(path)
node.isWord = False
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
return
tmp = board[i][j]
node = node.children.get(tmp)
if not node:
return
board[i][j] = "#"
self.dfs(board, node, i+1, j, path+tmp, res)
self.dfs(board, node, i-1, j, path+tmp, res)
self.dfs(board, node, i, j-1, path+tmp, res)
self.dfs(board, node, i, j+1, path+tmp, res)
board[i][j] = tmp
यदि किसी के पास मेरे प्रश्न पर प्रदर्शन और टिप्पणी में सुधार करने के लिए कोई अच्छा विचार है, तो यह बहुत अच्छा होगा। धन्यवाद। :) –
लीटकोड से ऐसे परिचित प्रश्न :) – stanleyli