华为OD机考题目分享（0517）
第二道题目：单词接龙
题目描述：
单词接龙的规则是：用于接龙的单词首字母要与前一个单词的尾字母相同；当存在多个可接龙的单词时，取长度最长的单词，如果长度也相同，则取字典序最小的单词；已经参与接龙的单词不能重复使用。
现给定一组全部由小写字母组成单词词组，并指定其中一个单词作为起始单词，进行单词接龙，现输出最长的单词串，单词串是单词拼接而成，中间没有空格。
输入描述：
输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0<=K<N；
输入的第二行为一个非负整数，表示一个单词的个数N；
接下来的N行，分别表示单词数组中的单词。
输出描述：
输出一个字符串，表示最终拼接的单词串
示例：
输入：
0
6
word
dd
da
dc
dword
d
输出：
worddwordda
from collections import defaultdict
k=int(input('请输入一个非负整数：'))
n=int(input('请输入一个非负整数：'))
words=defaultdict(list)
start=None
for i in range(n):
word=input('请输入接龙的单词：')
if i==k:
start=word
else:
words[word[0]].append((-len(word),word)) # 按单词首字母存储单词及单词的长度（负）
for key in words.keys():
words[key]=sorted(words[key]) # 字典的value按长度倒序和和单词字典序排序
while start is not None:
print(start,end='')
if len(words[start[-1]])==0:
break
start=words[start[-1]].pop(0)[1]
