华为OD机考真题--单词接龙--带答案

2023华为OD统一考试（A+B卷）题库清单-带答案（持续更新）or2023年华为OD真题机考题库大全-带答案（持续更新）

题目描述：

单词接龙的规则是：

用于接龙的单词首字母必须要前一个单词的尾字母相同；
当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；
已经参与接龙的单词不能重复使用。
现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙。

请输出最长的单词串，单词串是单词拼接而成，中间没有空格。

输入描述：

输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N。
输入的第二行为一个非负整数，表示单词的个数N。
接下来的N行，分别表示单词数组中的单词。
输出描述：

输出一个字符串，表示最终拼接的单词串。
备注：

单词个数N的取值范围为[1, 20]
单个单词的长度的取值范围为[1, 30]
————————————————

示例

输入：

0
6
word
dd
da
dc
dword
d
输出：

worddwordda
说明：

先确定起始单词word，再接以d开头的且长度最长的单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出worddwordda。
输入：

4
6
word
dd
da
dc
dword
d
输出：

dwordda
说明：

先确定起始单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出dwordda。
 

public class WordRelay {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int beginIndex = Integer.parseInt(sc.nextLine());int wordNums = Integer.parseInt(sc.nextLine());String [] word = new String[wordNums];List<Word> wordInfo = new LinkedList<>();for (int i = 0; i < wordNums; i++){word[i] = sc.next();if (i != beginIndex){wordInfo.add(new Word(word[i].length(),word[i]));}}find(word,beginIndex,wordInfo);}/*** 给List<Word>排序，初始化准备* @param word* @param beginIndex* @param wordInfo*/public static void find(String[] word, int beginIndex , List<Word> wordInfo ){Collections.sort(wordInfo, (o1, o2) -> {if (o1.length != o2.length){return o2.length - o1.length;}else {return o1.word.compareTo(o2.word);}});//起始值String beginWord = word[beginIndex];String endSingleWord = beginWord.substring(beginWord.length()-1,beginWord.length());StringBuffer sb = new StringBuffer();sb.append(beginWord);appendWord(wordInfo, endSingleWord, sb,true);}/*** 从大到小的长度顺序拼接* @param wordInfo* @param endSingleWord* @param sb* @param end*/private static void appendWord(List<Word> wordInfo, String endSingleWord, StringBuffer sb,Boolean end) {while (end){end = false;for (int i = 0; i < wordInfo.size(); i++){if (endSingleWord.equals(String.valueOf(wordInfo.get(i).word.charAt(0)))){sb.append(wordInfo.get(i).word);endSingleWord = wordInfo.get(i).word.substring(wordInfo.get(i).word.length()-1,wordInfo.get(i).word.length());//添加完移除wordInfo.remove(i);end = true;break;}}}System.out.println(sb.toString());}@Datapublic static class Word{int length;String word;public Word(int length, String word) {this.length = length;this.word = word;}}
}