<p>我只是好奇,是否有一种方法可以比较两种数据结构的相似性</p>
<pre><code>trie1 trie2
root root
/ | / |
m b m b
| | | |
a o a o
| \ | | |
t x b x b
def compare_trie(trie1, trie2):
pass
Output["max","bob"]
</code></pre>
<p>编辑:到目前为止,我试图实现dfs算法,但突然想到如何管理两个不同尝试的堆栈</p>
<p>我尝试过的代码仍然通过为两次不同的尝试管理两个堆栈来实现:</p>
<pre><code>def compareTrie(trie1, trie2):
dfsStack = []
result = []
stack1 = [x for x in trie1.keys()]
stack2 = [y for y in trie2.keys()]
similar = list(set(stack1) & set(stack2))
dfsStack.append((similar, result))
while (dfsStack):
current, result = dfsStack.pop()
print(current, result)
result.append(current)
for c in current:
trie1 = trie1[c]
trie2 = trie2[c]
st1 = [x for x in trie1.keys()]
st2 = [x for x in trie2.keys()]
simm = list(set(st1) & set(st2))
dfsStack.append((simm, result))
print(result)
</code></pre>
<p>Trie实施:</p>
<pre><code>def create_trie(words):
trie = {}
for word in words:
curr = trie
for c in word:
if c not in curr:
curr[c] = {}
curr = curr[c]
# Mark the end of a word
curr['#'] = True
return trie
s1 = "mat max bob"
s2 = "max bob"
words1 = s1.split()
words2 = s2.split()
t1 = create_trie(words1)
t2 = create_trie(words2)
</code></pre>