最大的绳子，可能是什么

Question

我有一张单子

list=["apple","white","loop","edit","tow","took","know"]

我想要打印，最长的字符串（下一个单词以previus的最后一个字母开始），不改变单词的顺序，比如：

4

（苹果，编辑，拍摄，知道） 我不能做（苹果，编辑，拿走，知道，白色），因为我需要改变顺序

Answer 1

一个可能的解决方案，在O（n）时间内运行：

我们追踪最后一封信中最长的链子。如果每个新词的第一个字母不是任何链的末端，则可以开始一个新链，或者添加到已找到的以该字母结尾的最长链中。你知道吗

反过来，这个新的链子可能是以当前单词的最后一个字母结尾的最长的链子，或者我们可以丢弃它。你知道吗

最后，我们只需要保留最长的链条。你知道吗

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'] 

请注意，我将您的原始列表重命名为words，因为命名它list会掩盖相同名称的Python内置。你知道吗

Answer 2

我洗澡的时候在想这个问题，我想出了一个解决办法。回到这个问题，我发现Thierry Lathuille's answer已经包含了相同的基本算法。但我认为我的实现稍微优化了一点，也稍微有点像python：

def longest_chain(words):
    chains = defaultdict(list)
    longest = []
    for word in reversed(words):
        first_char = word[0]
        last_char = word[-1]
        chain = chains[last_char] + [word]
        if len(chain) > len(chains[first_char]):
            chains[first_char] = chain
        if len(chain) > len(longest):
            longest = chain
    return list(reversed(longest))

这个实现实际上返回最长的链，尽管您可以很容易地将其简化为只跟踪长度（如果您需要的话）。你知道吗

恭喜你成功的nerd-sniped我！你知道吗

Answer 3

list = ["apple","white","loop","edit","tow","took","know"] , answer = 4

• 我们可以用动态规划的方法来解决这个问题。你知道吗
• 在这里，我们可以采用自下而上的方法，这意味着我们将从数组中的最后一个元素转到第一个元素。你知道吗
• 所以，我们从know开始，我们知道know前面什么都没有。所以，我们把它的值设为1。你知道吗
• 接下来我们来看took。took有know来建立您所描述的连接。所以，现在对于took，值是2（因为链中有两个单词）。你知道吗
• 最后，我们将为您的列表提供一个值数组[4,4,1,3,1,2,1]。你知道吗
• 现在，我们只需要取数组中这些值的最大值，这就是我们的答案。你知道吗
• 注意，为了得到一个单词的链长值，你需要得到所有可能链中的max。你知道吗

伪代码（因为我不是python爱好者）：

chain_lengths = new int[words.length]
max_length = 0
for i = words.length - 1 to 0
   chain_lengths[i] = 1
   for  j = i + 1 to words.length
      if last_char(words[i]) == first_char(words[j]):
         chain_lengths[i] = max(chain_lengths[i],chain_lengths[j] + 1)
   max_length = max(chain_lengths[i],max_length)

print max_length

• 时间复杂度：O（n^2）
• 空间复杂度：O（n）
• 请注意，这也可以确保单词的顺序是完整的。你知道吗

在实际Python中：

words = ["apple","white","loop","edit","tow","took","know"]

chain_lengths = [None]*len(words)
max_length = 0
for i in range(len(words)-1,-1,-1):
   chain_lengths[i] = 1
   for j in range(i+1, len(words)):
      if words[i][-1] == words[j][0]:
         chain_lengths[i] = max(chain_lengths[i],chain_lengths[j] + 1)
   max_length = max(chain_lengths[i],max_length)