华为OD -单词接龙（Python）

单词接龙

1. 题目描述

单词接龙的规则是:

可用于接龙的单词,首字母必须要与前一个单词的尾字母相同；

当存在多个首字母相同的单词时，取长度最长的单词；

如果长度也相等，则取字典序最小的单词；

已经参与接龙的单词不能重复使用；

现给定一组全部由小写字母组成的单词数组，

并指定其中一个单词为起始单词，进行单词接龙，

请输出最长的单词串。

单词串是单词拼接而成的，中间没有空格。

单词个数 1 < N < 20

单个单词的长度 1 ~ 30

1. 输入描述

输入第一行为一个非负整数

表示起始单词在数组中的索引k

0 <= k < N

输入的第二行为非负整数N

接下来的N行分别表示单词数组中的单词

1. 输出描述

输出一个字符串表示最终拼接的单词串

示例一

输入

0
6
word
dd
da
dc
dword
d

输出

worddwordda

示例一

输入

4
6
word
dd
da
dc
dword
d

输出

dwordda

1. 上代码

# !E:\pythonScript\venv python3
# -*- coding: utf-8 -*-
"""
Date: 2023/3/15
Time: 15:20
Author: kang
"""
def chains(start_index, words):
    builder = []
    builder.append(words[start_index])
    words.pop(start_index)
    words.sort(key=lambda x: (-len(x), x)) #第一个关键字是按字符串长度排序，通过 -len(x) 实现。因为默认情况下 sorted 函数是按升序排列的，因此需要使用负数来表示降序排列。
    while True:
        length = len(builder)
        last_word = builder[-1][-1]
        for i in range(len(words)):
            w = words[i]
            if w.startswith(last_word):
                builder.append(w)
                words.pop(i)
                break
        if len(builder) == length:
            break
        print(''.join(builder))


if __name__ == "__main__":
    start_index = int(input())
    number_word = int(input())
    words = []
    for i in range(number_word):
        words.append(input())
    chains(start_index, words)

1. 代码解释：

while这段代码实现了单词拼接的核心逻辑。具体来说，代码中的 while 循环会不断尝试在 builder 中添加新的单词，直到无法添加为止。循环中的每一轮通过查找以上一个单词结尾的单词来进行拼接，具体实现如下：

• length = len(builder)：记录循环开始前字符串 builder 的长度。

• last_word = builder[-1][-1]：获取当前 builder 中最后一个单词的最后一个字符，用于作为下一个待拼接单词的匹配条件。

• for i in range(len(words)): ...：遍历所有未使用的单词，查找以 last_word 开头的单词。

• w = words[i]：获取当前待匹配的单词。

• if w.startswith(last_word): ...：如果当前单词以 last_word 开头，则将其添加到 builder 中，并从 words 中删除该单词。

• if len(builder) == length: break：如果当前循环中没有添加新的单词，则退出循环。循环结束后，builder 中包含了所有已经拼接好的单词，将其通过 ''.join(builder) 方法连接起来即可得到最终输出。需要注意的是，在循环过程中可以通过 print(''.join(builder)) 语句输出中间结果，方便调试和理解程序逻辑。