擅长:python、mysql、java
<p>您使用dfs的想法是正确的;但是,您可以选择一种简单的递归方法来解决手头的任务。以下是递归版本:</p>
<pre class="lang-py prettyprint-override"><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
def compare(trie1, trie2, curr):
for i in trie1.keys():
if trie2.get(i, None):
if i=="#":
result.append(curr)
else:
compare(trie1[i], trie2[i], curr+i)
s1 = "mat max bob temp2 fg f r"
s2 = "max bob temp fg r c"
words1 = s1.split()
words2 = s2.split()
t1 = create_trie(words1)
t2 = create_trie(words2)
result = []
compare(t1, t2, "")
print(result) #['max', 'bob', 'fg', 'r']
</code></pre>