AcWing 1117. java单词接龙
原题链接
简单
作者:
mkuiwu
,
2021-02-13 00:10:52
,
所有人可见
,
阅读 489
import java.lang.*;
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer stz = new StringTokenizer("");
static String nextLine() throws Exception {// 读取下一行字符串
return br.readLine();
}
static String next() throws Exception {// 读取下一个字符串
while (!stz.hasMoreTokens()) {
stz = new StringTokenizer(br.readLine());
}
return stz.nextToken();
}
static int nI() throws Exception {// 读取下一个int型数值
return Integer.parseInt(next());
}
static double nD() throws Exception {// 读取下一个double型数值
return Double.parseDouble(next());
}
static long nL() throws Exception {// 读取下一个double型数值
return Long.parseLong(next());
}
static void write(String str) throws Exception{
bw.write(str);
}
static String itoS(int i){
return Integer.toString(i);
}
static void wI(int i) throws Exception{
write(Integer.toString(i));
}
static void wL() throws Exception{
write("\n");
}
static void flush() throws Exception{
bw.flush();
}
public void print() throws Exception{
flush();
}
public static void main(String[] args) throws Exception{
Main main = new Main(); main.run(); main.print();
}
final int N = 25;
int[][] g = new int[N][N];
int[] used = new int[N];
int n;
int res;
String[] word = new String[N];
void dfs(String curWord, int last){
// 更新一下结果数组
res = Math.max(curWord.length(), res);
used[last]++;
// 更新所有方向
for (int i = 0; i < n; i++) {
// 1. 没有交集
if (g[last][i] != 0 && used[i] < 2){
// 2. 使用次数超过两次
int k = g[last][i];
dfs(curWord + word[i].substring(k), i);
}
}
used[last]--;
}
public void run() throws Exception{
n = nI();
for (int i = 0; i < n; i++) {
word[i] = nextLine();
}
// 1. 求前缀和数组
for (int i = 0; i < n; i++) {
String a = word[i];
// 感觉求一遍就可以了 一样的
for (int j = 0; j < n; j++) {
String b = word[j];
// 然后还要个长度数组的 经典写法
for (int k = 1; k < Math.min(a.length(), b.length()); k++) {
if (a.substring(a.length() - k, a.length() ).equals(b.substring(0,k))){
// 直接存 k 就可以了, 不一定要存下标
g[i][j] = k;
break; // 找到第一个即可
}
}
}
}
char h = nextLine().charAt(0);
// 找到初始字符串加入dfs
for (int i = 0; i < n; i++) {
if (word[i].charAt(0) == h){
dfs(word[i], i);
}
}
wI(res); wL();
}
}