算法分析
-
1、通过贪心的思想,两个字符串拼接,重合部分越短,拼接后的长度越长,因此,需要预处理出所有单词两两拼接重合的最小长度,
g[][]
表示i
位置子符串与j
位置子符串拼接重合的最小长度 -
2、从给定的字符开始,确定单词龙的第一个单词,向所有能够拼接到第一个单词后面的单词进行深度优先遍历
-
3、
dfs(dragon,last)
:dragon
表示当前的单词龙,last
表示上一个连接到字符串的单词
参考文献
算法提高课
Java 代码
import java.util.Scanner;
public class Main {
static int N = 21;
static int n;
static String[] word = new String[N];
static int[][] g = new int[N][N];//表示i位置子符串与j位置子符串拼接重合的最小长度
static int[] used = new int[N]; //i位置的字符串的使用次数
static int res = 0;
//dragon表示当前的单词龙,last表示上一个连接到字符串的单词
static void dfs(String dragon,int last)
{
res = Math.max(dragon.length(), res);
for(int i = 0;i < n;i ++)
{
if(g[last][i] > 0 && used[i] < 2)
{
int k = g[last][i];
used[i] ++;
dfs(dragon + word[i].substring(k),i);
used[i] --;
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 0;i < n;i ++) word[i] = scan.next();
String start = scan.next();
//预处理
for(int i = 0;i < n;i ++)
for(int j = 0;j < n;j ++)
{
String a = word[i];
String b = word[j];
for(int k = 1;k < Math.min(a.length(), b.length());k ++)
{
int lenA = a.length() ;
int lenB = b.length() ;
if(a.substring(lenA - k, lenA).equals(b.substring(0, k)))
{
g[i][j] = k;
break;
}
}
}
for(int i = 0;i < n;i ++)
{
//若该单词的第一字母和start相同
if(word[i].substring(0, 1).equals(start))
{
used[i] ++;//表示该单词已使用一次
dfs(word[i],i);
used[i] --;
}
}
System.out.println(res);
}
}