当前位置：首页 > news >正文

【华为OD-E卷 - 单词接龙 100分（python、java、c++、js、c）】

news 来源：原创 2025/8/9 19:27:41

【华为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 heapqdef 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(""); // 拼接单词返回最终结果
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏