ALGO-18 单词接龙 (蓝桥杯算法基础训练)(java版)
试题 算法训练 单词接龙 资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数n (n<=20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式
只需输出以此字母开头的最长的“龙”的长度
样例输入
5
at
touch
cheat
choose
tact
a
样例输出
23
样例说明
连成的“龙”为atoucheatactactouchoose
基本思路 ( DFS + 回溯 )
- 【ALGO-18 单词接龙 (蓝桥杯算法基础训练)(java版)】计算每个单词之间是有关系 (能不能被接龙 , 以及相同的单词部分是多少)
- 计算完之后会形成一个有向图 ( 如图 )
文章图片
- 通过深度优先+回溯 获得最长的 单词组合
代码演示
import java.io.*;
import java.util.*;
class Main {
ReadIn readIn = new ReadIn(System.in);
PrintWriter printWriter = new PrintWriter(System.out, true);
int num;
//单词数量
String[] map;
//保存每个单词
int[] flag;
//每个单词出现的次数
int[][] diff;
//记录一个单词和另一个单词的相同字母的个数
int max = 0;
//最长字母public void run() throws IOException {
num = readIn.nextInt();
map = new String[num];
flag = new int[num];
diff = new int[num][num];
for (int i = 0;
i < num;
i++) {
map[i] = readIn.next();
}String startString = readIn.next();
//开头的for (int i = 0;
i < num;
i++) {//比较每个单词
for (int j = 0;
j < num;
j++) {
int len = Math.min(map[i].length(), map[j].length());
//最2个长度最小的
for (int k = 1;
k < len;
k++) {
if (map[i].substring(map[i].length() - k)
.equals(map[j].substring(0, k))) {
diff[i][j] = k;
break;
}
}
}
}for (int i = 0;
i < num;
i++) {
if (map[i].startsWith(startString)) {
dfs(i, map[i].length());
}
}System.out.println(max);
}private void dfs(int start, int len) {
flag[start]++;
//使用了1次
for (int i = 0;
i < num;
i++) {
if(diff[start][i]!=0 && flag[i] < 2)
dfs(i,len + map[i].length() - diff[start][i]);
}
flag[start] -- ;
//回溯
max = Math.max(max,len);
}public static void main(String[] args) throws IOException {
new Main().run();
}static class ReadIn {
private StringTokenizer stringTokenizer;
private BufferedReader bufferedReader;
public ReadIn(InputStream inputStream) {
bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
stringTokenizer = new StringTokenizer("");
}public String next() throws IOException {
if (!stringTokenizer.hasMoreTokens()) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
}
return stringTokenizer.nextToken();
}public int nextInt() throws IOException {
return Integer.parseInt(next());
}public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}}
样本测试
文章图片
感谢观看
来自一个萌新的呐喊~~
欢迎大佬们提出更好的思路
推荐阅读
- 爱的传递|爱的传递 | 儿文群故事接龙
- 背单词是噩梦(不着急,比“红宝书”更好的记忆单词的方法来了!——从词源的角度记单词(二))
- 墨墨单词/2018.3.6/
- 小组内部金句接龙4
- SCI论文写作怎样巧用英语单词--Editideas(辑思编译)
- 汤世声(学好英语,从提高记忆力开始)
- 语音篇?重读位置(七)
- 2018.05.08
- 【我们一起,向前一步】我们苏州见!聚会大接龙()|【我们一起,向前一步】我们苏州见!聚会大接龙:) (下))
- Android命名规范