华为OD E卷（100分）44-单次接龙
前言
工作了十几年，从普通的研发工程师一路成长为研发经理、研发总监。临近40岁，本想辞职后换一个相对稳定的工作环境一直干到老, 没想到离职后三个多月了还没找到工作，愁肠百结。为了让自己有点事情做，也算提高一下自己的编程能力，无聊之余打算用一些大厂的编程题练练手。希望通过这些分享能够帮到一些人，也希望能和看到此文的大神们沟通交流，提升自己，更希望在此期间能够找到一份理想的工作。
题目描述
单词接龙的规则是：
- 可用于接龙的单词首字母必须要前一个单词的尾字母相同；
- 当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；
- 已经参与接龙的单词不能重复使用。
现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，请输出最长的单词串，单词串是单词拼接而成，中间没有空格。
输入
输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ；
输入的第二行为一个非负整数，表示单词的个数N；
接下来的N行，分别表示单词数组中的单词。备注：
单词个数N的取值范围为[1, 20]；
单个单词的长度的取值范围为[1, 30]；
输出
输出一个字符串，表示最终拼接的单词串。
示例
示例1
输入
0
6
word
dd
da
dc
dword
d
输出worddwordda
说明：先确定起始单词word，再接以d开头的且长度最长的单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出worddwordda。
示例2
输入
4
6
word
dd
da
dc
dword
d
输出dwordda
说明：
先确定起始单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出dwordda。
解题思路
使用TreeSet存储单词，天然按字符顺序排序。
题解
Java实现
package huawei.e100;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
/**
* @author arnold
* @date 2025年1月2日
* 单次接龙
*/
public class T44 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int index = sc.nextInt();
int num = sc.nextInt();
String start = null;
Set<String> words = new TreeSet<>();
sc.nextLine();
for (int i = 0; i < num; i++) {
String word = sc.nextLine().trim();
words.add(word);
if (i == index) {
start = word;
}
}
String s = run(words, start);
System.out.println(s);
}
}
static String run(Set<String> words, String start){
StringBuilder sb = new StringBuilder();
sb.append(start);
words.remove(start);
while(words.size() > 0 ) {
Iterator<String> it = words.iterator();
String next = null;
while(it.hasNext()) {
String w = it.next();
if(w.charAt(0) == start.charAt(start.length()-1)) {
if(next == null) {
next = w;
} else {
if(w.length() > next.length()) {
next = w;
}
}
}
}
if(next != null) {
sb.append(next);
words.remove(next);
start = next;
} else {
break;
}
}
return sb.toString();
}
}