擅长:python、mysql、java
<p>一个可能的解决方案,在O(n)时间内运行:</p>
<p>我们追踪最后一封信中最长的链子。如果每个新词的第一个字母不是任何链的末端,则可以开始一个新链,或者添加到已找到的以该字母结尾的最长链中。你知道吗</p>
<p>反过来,这个新的链子可能是以当前单词的最后一个字母结尾的最长的链子,或者我们可以丢弃它。你知道吗</p>
<p>最后,我们只需要保留最长的链条。你知道吗</p>
<pre><code>words = ["apple","white","loop","edit","tow","took","know"]
found_ends = {}
for word in words:
if word[0] in found_ends:
# This word can make a chain longer
new_chain = found_ends[word[0]] + [word]
else:
# We start a new one
new_chain = [word]
# Is it the new longest chain for an end letter?
if word[-1] not in found_ends or len(found_ends[word[-1]]) < len(new_chain):
found_ends[word[-1]] = new_chain
print(max(found_ends.values(), key=len))
# ['apple', 'edit', 'took', 'know']
</code></pre>
<p>请注意,我将您的原始列表重命名为<code>words</code>,因为命名它<code>list</code>会掩盖相同名称的Python内置。你知道吗</p>