【华为OD-E卷 - 单词接龙 100分（python、java、c++、js、c）】
题目
单词接龙的规则是：
可用于接龙的单词首字母必须要前一个单词的尾字母相同； 当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；已经参与接龙的单词不能重复使用。 现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，
请输出最长的单词串，单词串是单词拼接而成，中间没有空格
输入描述
- 输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ； 输入的第二行为一个非负整数，表示单词的个数N； 接下来的N行，分别表示单词数组中的单词
输出描述
- 输出一个字符串，表示最终拼接的单词串
备注
- 单词个数N的取值范围为[1, 20]； 单个单词的长度的取值范围为[1, 30]
用例
用例一：
输入：
0
6
word
dd
da
dc
dword
d
输出：
worddwordda
用例二：
输入：
4
6
word
dd
da
dc
dword
d
输出：
dwordda
python解法
- 解题思路：
- 解析输入
读取标准输入 sys.stdin.read() 并用 split() 按空格分割成 data 列表。
data[0] 为起始索引 k，data[1] 为单词数量 n，data[2:] 为 n 个单词组成的列表 words。
构造最长单词链
初始化：
result 存储最终的单词链，从索引 k 的单词开始。
words[k] 设为 None，表示已使用。
使用 groups 组织未使用的单词，以首字母为键，将同一首字母的单词存入 最大堆（heapq 的 Python 版本默认是最小堆，存入时取负号转换为最大堆）。
构造最长链：
取 result[-1] 的最后一个字母 last_char，从 groups 取出最长的可连接单词 nxt，并加入 result。
若 last_char 在 groups 但 heapq 为空，则终止构造。
返回结果
将 result 列表拼接成字符串并返回。
使用到的算法
最大堆（heapq）
用 heapq.heappush(groups[w[0]], (-len(w), w)) 维护每个首字母对应的最长单词，以 负长度 存储保证堆顶是最长的单词。
贪心策略
每次从 groups 选择最长的符合条件的单词，以最大化单词链长度。
哈希表（字典 groups）
使用 dict 以 首字母 作为键，快速查找可连接单词
import sys
import heapq
def build_longest_chain(start_idx, words):
"""
构造最长的单词链
:param start_idx: 起始单词索引
:param words: 单词列表
:return: 拼接后的最长单词链字符串
"""
result = [words[start_idx]] # 以索引 start_idx 的单词作为链的起点
words[start_idx] = None # 标记该单词为已使用
groups = {} # 以首字母为键，存储未使用的单词（按长度降序）
# 构造 groups 字典：按首字母分类并存入最大堆
for w in words:
if w is not None: # 跳过已使用的单词
if w[0] not in groups:
groups[w[0]] = []
heapq.heappush(groups[w[0]], (-len(w), w)) # 按长度降序存储
# 逐步构造最长的单词链
while True:
last_char = result[-1][-1] # 取当前链的最后一个字符
if last_char in groups and groups[last_char]: # 若存在以 last_char 开头的单词
_, nxt = heapq.heappop(groups[last_char]) # 取出最长的单词
result.append(nxt) # 添加到链中
else:
break # 无法继续延续单词链时终止
return "".join(result) # 拼接单词返回最终结果
def main():
"""
读取输入并调用构造函数
"""
data = sys.stdin.read().split() # 读取输入并按空格分割
k = int(data[0]) # 读取起始索引
n = int(data[1]) # 读取单词数量
words = data[2:] # 读取单词列表
print(build_longest_chain(k, words)) # 计算最长单词链并输出
if __name__ == "__main__":
main()
java解法
- 解题思路
- 解析输入
使用 Scanner 读取输入：
k：起始索引
n：单词总数
words[]：单词数组
构造最长单词链
初始化
result 存储最终的单词链，以索引 k 位置的单词作为起点。
words[startIdx] = null; 标记该单词已使用。
groups 是一个 Map<Character, PriorityQueue>，按首字母分类，PriorityQueue 以单词长度降序排序（相同长度按字典序）。
构造最长链
取 result 最后一个单词的末尾字符 lastChar，从 groups 取出最长的可连接单词 next 并加入 result。
若 groups.get(lastChar) 为空，则终止构造。
返回结果
将 result 列表拼接成字符串并返回。
使用到的算法
优先队列（PriorityQueue）
维护每个首字母对应的最长单词，保证每次取出的单词是最长的，若长度相同按字典序排列。
贪心策略
每次选择 最长的 符合条件的单词，以最大化单词链长度。
哈希表（Map<Character, PriorityQueue>）
Map 以首字母为键，快速查找可连接的单词队列。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取起始索引和单词总数
int k = sc.nextInt();
int n = sc.nextInt();
String[] words = new String[n];
// 读取单词
for (int i = 0; i < n; i++) words[i] = sc.next();
// 计算并输出最长单词链
System.out.println(buildLongestChain(k, words));
}
/**
* 构造最长的单词链
* @param startIdx 起始单词索引
* @param words 输入的单词数组
* @return 拼接后的最长单词链字符串
*/
public static String buildLongestChain(int startIdx, String[] words) {
List<String> result = new ArrayList<>();
result.add(words[startIdx]); // 以索引 startIdx 的单词作为链的起点
words[startIdx] = null; // 标记该单词为已使用
// 创建 Map，按首字母分类存储未使用的单词，并按长度降序排序（同长按字典序）
Map<Character, PriorityQueue<String>> groups = new HashMap<>();
for (String word : words) {
if (word != null) { // 跳过已使用的单词
char firstChar = word.charAt(0);
groups.putIfAbsent(firstChar, new PriorityQueue<>((a, b) ->
a.length() != b.length() ? b.length() - a.length() : a.compareTo(b)
));
groups.get(firstChar).offer(word); // 按长度降序加入队列
}
}
// 逐步构造最长的单词链
while (true) {
String lastWord = result.get(result.size() - 1);
char lastChar = lastWord.charAt(lastWord.length() - 1); // 取当前链的最后一个字符
if (groups.containsKey(lastChar) && !groups.get(lastChar).isEmpty()) {
result.add(groups.get(lastChar).poll()); // 取出最长的单词
} else {
break; // 无法继续延续单词链时终止
}
}
return String.join("", result); // 拼接单词返回最终结果
}
}
C++解法
- 解题思路
- 解析输入
读取 k（起始单词索引）和 n（单词总数）。
使用 getline(cin, words[i]) 逐行读取 n 个单词，存入 vector words。
构造最长单词链
初始化
以 words[k] 作为起始单词，存入 chain 。
从 words 中删除索引 k 处的单词，避免重复使用。
用 哈希表 prefix 按首字母分组，存储剩余单词。
对分组进行排序
对 prefix 的每个 vector 进行排序：
优先选择最长单词。
若长度相同，按字典序排序。
构造最长链
取 chain.back() 末尾字符 tail，在 prefix[tail] 找最长的单词，加入 chain。
若 prefix[tail] 为空，则终止构造。
返回结果
连接 chain 中所有单词，返回拼接后的字符串。
使用到的算法
哈希表（unordered_map<char, vector>）
以首字母为键，存储所有以该字母开头的单词列表，便于查找 可连接的最长单词。
贪心策略
优先选择最长的可连接单词，若长度相同，则按字典序排序。
排序（sort()）
按单词长度降序排序，确保最长单词优先。
若长度相同，按字典序排序。
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
/**
* 构造最长的单词链
* @param words 输入的单词数组
* @param k 起始单词索引
* @return 拼接后的最长单词链字符串
*/
string getResult(vector<string>& words, int k) {
vector<string> chain;
chain.push_back(words[k]); // 以索引 k 的单词作为链的起点
words.erase(words.begin() + k); // 删除该单词，避免重复使用
unordered_map<char, vector<string>> prefix; // 存储按首字母分组的单词
// 组织 prefix 以首字母分类
for (const string& word : words) {
char w = word[0];
prefix[w].push_back(word);
}
// 对每组单词排序：优先选择最长单词，若长度相同则按字典序排序
for (auto& [key, wordsList] : prefix) {
sort(wordsList.begin(), wordsList.end(), [](const string& a, const string& b) {
if (a.length() != b.length()) {
return a.length() > b.length(); // 长度降序
}
return a < b; // 字典序升序
});
}
// 逐步构造最长的单词链
while (true) {
char tail = chain.back().back(); // 取当前链的最后一个字符
if (prefix.count(tail) && !prefix[tail].empty()) {
chain.push_back(prefix[tail].front()); // 取最长的单词
prefix[tail].erase(prefix[tail].begin()); // 移除已使用的单词
} else {
break; // 无法继续延续单词链时终止
}
}
// 拼接单词返回最终结果
string result;
for (const string& word : chain) {
result += word;
}
return result;
}
int main() {
int k, n;
cin >> k >> n;
cin.ignore(); // 处理换行符
vector<string> words(n);
for (int i = 0; i < n; i++) {
getline(cin, words[i]); // 读取单词
}
// 计算并输出最长单词链
cout << getResult(words, k) << endl;
return 0;
}
C解法
更新中
JS解法
使用 readline 监听 stdin（标准输入）。
lines.push(line) 存储输入行：
第一行 k（起始单词索引）。
第二行 n（单词总数）。
接下来的 n 行是单词。
构造最长单词链
初始化
words.splice(k, 1) 取出索引 k 处的单词作为起点，存入 chain 。
其余单词按首字母分组存入 prefix 对象（哈希表）。
对分组进行排序
优先选择最长单词（长度降序）。
若长度相同，按字典序排序。
构造最长链
取 chain 最后一个单词的末尾字符 tail，从 prefix[tail] 取最长单词 next 并加入 chain。
若 prefix[tail] 为空，则终止构造。
返回结果
将 chain 列表拼接成字符串并返回。
使用到的算法
哈希表（prefix 对象）
以首字母为键，存储所有以该字母开头的单词列表，便于查找 可连接的最长单词。
贪心策略
优先选择最长的可连接单词，若长度相同，则按字典序排序。
排序（Array.sort()）
按单词长度降序排序，确保最长单词优先。
若长度相同，按字典序排序。
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
// 创建标准输入流监听
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
let k, n;
// 读取输入行
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
// 解析 k（起始索引）和 n（单词总数）
[k, n] = lines.map(Number);
}
if (n && lines.length === n + 2) {
lines.shift(); // 移除第一行（k）
lines.shift(); // 移除第二行（n）
// 计算并输出最长单词链
console.log(getResult(lines, k));
lines.length = 0; // 清空输入
}
});
/**
* 构造最长的单词链
* @param {string[]} words 输入的单词数组
* @param {number} k 起始单词索引
* @return {string} 拼接后的最长单词链字符串
*/
function getResult(words, k) {
const chain = words.splice(k, 1); // 以索引 k 的单词作为链的起点
const prefix = {}; // 存储按首字母分组的单词
// 组织 prefix 以首字母分类
for (let word of words) {
const w = word[0];
prefix[w] ? prefix[w].push(word) : (prefix[w] = [word]);
}
// 对每组单词排序：优先选择最长单词，若长度相同则按字典序排序
for (let key in prefix) {
prefix[key].sort((a, b) =>
a.length !== b.length ? b.length - a.length : a > b ? 1 : -1
);
}
// 逐步构造最长的单词链
while (true) {
let tail = chain.at(-1).at(-1); // 取当前链的最后一个字符
if (prefix[tail] && prefix[tail].length > 0) {
chain.push(prefix[tail].shift()); // 取最长的单词
} else {
break; // 无法继续延续单词链时终止
}
}
return chain.join(""); // 拼接单词返回最终结果
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏