华为OD机试真题——单词接龙（首字母接龙）（2025A卷：100分）Java/python/JavaScript/C/C++/GO最佳实现

2025 A卷 100分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《单词接龙（首字母接龙）》：

文章快捷目录

题目描述及说明

Java

python

JavaScript

C++

C

GO

更多内容

题目名称：单词接龙（首字母接龙）

知识点：字符串、贪心算法、逻辑处理
时间限制：1秒
空间限制：256MB
限定语言：不限

题目描述

给定一组由小写字母组成的单词数组，并指定其中一个单词作为起始单词，按照以下规则进行单词接龙，输出最长的拼接字符串（无空格）：

1. 接龙规则：每个后续单词的首字母必须与前一个单词的尾字母相同。
2. 选择优先级：当存在多个可选单词时，优先选择长度最长的；若长度相同，则选择字典序最小的。
3. 去重规则：已使用的单词不可重复使用。

输入描述：

• 第一行为起始单词的索引 K（0 ≤ K < N）。
• 第二行为单词总数 N（1 ≤ N ≤ 20）。
• 后续 N 行，每行一个单词（长度1~30）。

输出描述：
拼接后的最长单词串。

示例：
输入：

0  
6  
word  
dd  
da  
dc  
dword  
d  

输出：

worddwordda  

解释：起始单词 word → 接 dword（最长且首字母为 d）→ 剩余可选 dd、da、dc，选择字典序最小的 da。

Java

问题分析

题目要求根据给定的单词列表，从指定起始单词开始，按照首尾字母相同的规则进行接龙，选择时优先选最长的单词，长度相同则选字典序最小的，且每个单词只能用一次。目标是找到最长的拼接字符串。

解题思路

1. 深度优先搜索（DFS）：遍历所有可能的路径，记录最长拼接字符串。
2. 贪心剪枝：在每一步中按优先级处理候选单词（长度优先，字典序次之），尝试快速找到最优解。
3. 回溯：标记已使用的单词，递归结束后恢复状态，确保其他路径可被探索。

代码实现

import java.util.*;

public class Main {
   
    private static String maxStr = ""; // 存储最长结果
    private static int maxLen = 0;     // 最长字符串长度
    private static int totalLen = 0;    // 所有单词总长度（用于剪枝）

    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.nextLine()); // 起始单词索引
        int n = Integer.parseInt(sc.nextLine()); // 单词总数
        String[] words = new String[n];
        for (int i = 0; i < n; i++) {
   
            words[i] = sc.nextLine().trim();
        }

        // 计算所有单词总长度
        for (String word : words) {
   
            totalLen += word.length();
        }

        boolean[] used = new boolean[n]; // 记录单词是否被使用
        String startWord = words[k];
        used[k] = true;
        maxStr = startWord;
        maxLen = startWord.length();

        dfs(startWord, startWord.charAt(startWord.length() - 1), used, words, startWord.length());
        System.out.println(maxStr);
    }

    private static void dfs(String currentStr, char lastChar, boolean[] used, String[] words, int usedLen) {
   
        // 更新最长结果
        int currentLen = currentStr.length();
        if (currentLen > maxLen || (currentLen == maxLen && currentStr.compareTo(maxStr) < 0)) {
   
            maxStr = currentStr;
            maxLen = currentLen;
        }

        // 剪枝：当前长度 + 剩余单词总长度 <= 已找到的最大长度，无需继续
        int remaining = totalLen - usedLen;
        if (currentLen + remaining <= maxLen) {
   
            return;
        }

        // 收集所有可用的候选单词（首字母匹配且未被使用）
        List<Candidate> candidates = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
   
            if (!used[i] && words[i].charAt(0) == lastChar) {
   
                candidates.add(new Candidate(words[i], i));
            }
        }

        // 按长度降序、字典序升序排序
        Collections.sort(candidates, (a, b) -> {
   
            if (a.word.length() != b.word.length()) {
   
                return Integer.compare(b.word.length(), a.word.length());
            } else {
   
                return a.word.compareTo(b.word);
            }
        });

        // 递归处理每个候选
        for (Candidate c : candidates) {
   
            String word = c.word;
            int idx = c.index;
            used[idx] = true; // 标记为已用
            dfs(currentStr + word, word.charAt(word.length() - 1), used, words, usedLen + word.length());
            used[idx] = false; // 回溯
        }
    }

    // 辅助类，记录单词及其索引
    static class Candidate {
   
        String word;
        int index;

        Candidate(String word, int index) {
   
            this.word = word;
            this.index = index;
        }
    }
}

代码解析

1. 全局变量：

   • maxStr：记录当前最长的拼接字符串。
   • maxLen：记录最长字符串的长度。
   • totalLen：所有单词的总长度，用于剪枝。

2. 输入处理：

   • 读取起始索引 k 和单词列表，初始化 used 数组标记起始单词为已使用。

3. DFS函数：

   • 更新最长字符串：比较当前拼接长度，更新 maxStr 和 maxLen。
   • 剪枝：若当前长度加上剩余单词总长度无法超过已知最长长度，提前返回。
   • 候选单词收集：筛选所有首字母匹配且未被使用的单词。
   • 排序：按长度降序和字典序升序排列候选单词。
   • 递归处理：依次选择每个候选单词，标记为已用，递归调用后回溯。

4. Candidate类：

   • 记录单词及其索引，方便排序后回溯时恢复状态。<