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類：

   • 記錄單詞及其索引，方便排序后回溯時恢復狀態。<